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

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (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)까지 합을 구해 출력한다.

내 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

tbl = []
for _ in range(n):
    list1 = list(map(int, input().split()))
    tbl.append(list1)
   
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    sum1 = 0
    for i in range(x2-x1+1):
        sum1 += sum(tbl[x1-1+i][y1-1:y2])
    print(sum1)

처음에는 또 정직하게 이런 식으로 풀었다가 시간 초과가 떴다.
아래는 모범 풀이를 보며 다시 풀어서 제출하여 정답을 받은 코드.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

tbl = [[0]*(n+1)]
for _ in range(n):
    list1 = [0] + list(map(int, input().split()))
    tbl.append(list1)
    
cum = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        cum[i][j] = tbl[i][j] + cum[i][j-1] + cum[i-1][j] - cum[i-1][j-1]
         
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    answer = cum[x2][y2] - cum[x2][y1-1] - cum[x1-1][y2] + cum[x1-1][y1-1]
    print(answer)

코멘트

이 문제는 dp 유형이다. dp를 이용하지 않으면 최대 $1024^2 = 1,048,576$개라는 엄청난 수에서 구간 합을 구해야 하므로 시간 초과의 철퇴를 맞게 된다. dp 배열을 선언하여 미리 누적 합을 계산해두는 방식으로 풀면 된다.

우선 입력받은 표를 바탕으로 구간의 누적 합 배열 cum을 선언한다. (표를 입력 받을 때 [[0]*(n+1)]인 이유는 뒤의 규칙을 보면 (i-1)번째 열 등의 표현을 사용해야 하므로 0번째에 dummy 열/행을 만들어 두는 것이다.) (i, j)의 누적 합은 (i, j-1)의 누적 합 + (i-1, j)의 누적 합 - (i-1, j-1)의 누적합 + (i, j)의 값과 같다. (자세한 원리는 여기 참고) 이렇게 미리 구간의 누적 합 배열을 선언해두면 구간의 합을 구할 때 빠르게 계산할 수 있다.

(i1, j1)에서 (i2, j2)까지의 구간합은 (i2, j2)의 누적 합 - (i2, j1-1)의 누적 합 - (i1-1, j2)의 누적 합 + (i1-1, j1-1) 누적 합과 같다. 따라서 x1, y1, x2, y2를 입력받아서 cum을 이용해 구간합을 구할 수 있다.

References

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