[백준] 11660 구간 합 구하기 5

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제 입력

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력

27
6
64

풀이

기존 배열을 순회하면서, 현재 좌표를 포함하면서 좌측 상단의 모서리 부분(시작점)까지의 누적합을 차례로 저장했다.

따라서 (x1,y1)부터 (x2,y2)까지의 합은
(x2,y2)누적합 - ((x2,y1-1)누적합 + (x2-1,y2)누적합 - (x1-1,y1-1)누적합)) 이다. 이는 점화식의 형태로, 누적합 개념과 함께 dp 개념이 사용된다는 것을 볼 수 있다.

이때 x1, y1이 각각 0인지 아닌지에 따라 빼야할 누적합이 있을 수도 있고, 없을 수도 있다.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == 0 and j == 0: continue
        elif i == 0: arr[i][j] += arr[i][j-1]
        elif j == 0: arr[i][j] += arr[i-1][j]
        else: arr[i][j] += arr[i][j-1] + arr[i-1][j] -  arr[i-1][j-1]
        
for i in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
    default = arr[x2][y2] #기본값(0,0)일때 이것만 사용
    if y1>0: leftSum = arr[x2][y1-1] # y1 > 0 일때
    else: leftSum = 0
    if x1>0: topSum = arr[x1-1][y2] # x1 > 0 일때
    else: topSum = 0
    if x1>0 and y1>0: leftTopSum = arr[x1-1][y1-1] # x1 > 0 & y1 > 0 일때
    else: leftTopSum = 0
    
    print(default-(leftSum+topSum-leftTopSum))

풀이 2

타 블로거 분의 풀이를 보니 x1,y1의 좌표에 따라 예외를 처리하지 않고 애초에 답을 기록할 배열을 따로 (N+1) x (N+1) 배열로 만든 풀이를 사용하셨다.

0번째 행&열의 값을 모두 0으로 초기화한 뒤, 사용하면 기저상태가 설정이 되므로 예외 처리 없이 간단하게 처리할 수 있다.

아래엔 (N+1) x (N+1) 크기의 답 배열을 따로 생성했는데, 기존에 입력받은 값을 저장한는 배열을 (N+1) x (N+1) 로 만든 후 0번째 행&열의 값을 모두 0으로 초기화하면 아래 코드와 거의 동일해진다.

배열을 사용할때 문제의 좌표계가 (1,1)부터 시작할 경우 초기 or 답을 저장할 배열의 크기를 가로 세로 1씩 늘리는 것도 고려해보자.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

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

for i in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    print(dp[x2][y2]-(dp[x2][y1-1]+dp[x1-1][y2])+dp[x1-1][y1-1])