[백준]11660 구간 합 구하기 5 (python 파이썬)

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

---

구간 합 구하기 2차원 버전

---

아이디어

 

1. 누적 합 사용

• 구간 합 구하기 4와 유사하게 풀었다
• 먼저 (0 ,0)에서 (x , y)까지의 합을 arr [x][y]에 저장한다. 그럼 아래와 같은 리스트를 만들 수 있다.

• 이걸 사용해서 구간 합을 구하면 된다.
• 예를 들어 (1, 1)에서 (2, 3)까지 구하려면(문제에서는 2,2 ~ 3,4) arr [2][3]에서 arr[2][0]과 arr[0][3]를 빼고 arr[0][0]을 더해주면 된다.

---

전체 코드

import sys
N, M = map(int, input().split())

arr = []

for _ in range(N):
    arr.append([int(x) for x in sys.stdin.readline().rstrip().split()])

for i in range(N):
    for j in range(1, N):
        arr[i][j] += arr[i][j - 1]

for j in range(N):
    for i in range(1, N):
        arr[i][j] += arr[i - 1][j]
        
for _ in range(M):
    ans = 0
    x1, y1, x2, y2 = map(int, sys.stdin.readline().rstrip().split())

    x1 -= 1
    x2 -= 1
    y1 -= 1
    y2 -= 1 # 좌표 조정

    ans += arr[x2][y2]

    if x1 - 1 >= 0:
        ans -= arr[x1 - 1][y2]

    if y1 - 1 >= 0:
        ans -= arr[x2][y1 - 1]

    if x1 - 1 >= 0 and y1 - 1 >= 0:
        ans += arr[x1 - 1][y1 - 1]

    print(ans)

---

코드 설명

import sys
N, M = map(int, input().split())

arr = []

for _ in range(N):
    arr.append([int(x) for x in sys.stdin.readline().rstrip().split()])

for i in range(N):
    for j in range(1, N):
        arr[i][j] += arr[i][j - 1]

for j in range(N):
    for i in range(1, N):
        arr[i][j] += arr[i - 1][j]

위에 설명한 배열을 만드는 과정이다. 

2차원 배열에서 누적합을 구하려면 행을 기준으로 한번, 열을 기준으로 한번 누적해서 더해주면 된다.

 

for _ in range(M):
    ans = 0
    x1, y1, x2, y2 = map(int, sys.stdin.readline().rstrip().split())

    x1 -= 1
    x2 -= 1
    y1 -= 1
    y2 -= 1 # 좌표 조정

    ans += arr[x2][y2]

    if x1 - 1 >= 0:
        ans -= arr[x1 - 1][y2]

    if y1 - 1 >= 0:
        ans -= arr[x2][y1 - 1]

    if x1 - 1 >= 0 and y1 - 1 >= 0:
        ans += arr[x1 - 1][y1 - 1]

    print(ans)

문제에서는 (1,1)부터 시작이므로 각 좌표에서 -1 해준다.

 

그리고 위에서 설명한 연산을 수행하면 된다.

단, 배열의 index를 넘어가면 안 되므로 조건을 추가해서 수행한다.