Ray`s Tech Lab

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

주어진 정사각형 모양의 표에서 좌표 2개로 주어지는 특정 영역의 합을 구하는 문제.

(x1, y1)과 (x2, y2)로 주어지는 두 좌표에 대해 x1 <= x2, y1 <= y2가 성립하며 표는 최대 1024 * 1024사이즈이고 최대 100,000번의 합을 구해야 한다.

무식하게 즉 브루트한 방법으로 푼다면 M번의 트라이에 대해 그 때마다 반복문을 돌며 처리할 수 있다. 그러나 이 방법으로 한다면 최악의 경우 100,000 * 1024 * 1024번의 연산을 해야 하며, 주어진 시간인 1초 내에 통과할 수 없을 것이다.

매번 새로 합을 구하는 것이 아니라 이전에 구한 값을 재활용하는 DP를 통해 문제에 접근해야 한다는 생각이 들었다. 그러나 K번째 트라이에 대한 답을 구할 때 이전 트라이에서 구한 답을 이용해 구할 수 있을지는..

그러다가 풀이방법이 떠올랐다. 누적합을 이용하는 것이다. sum[r][c]가 (0, 0)에서 (r, c)까지의 영역의 합을 의미한다고 하고 (0, 0)부터 (N, N)까지의 모든 sum값을 구해뒀다고 하자. 그렇다면 이를 활용해 임의의 두 좌표 (x1, y1)부터 (x2, y2)의 영역의 합을 sum값을 이리저리 활용해 구할 수 있다! 이 sum값을 구할 때 내가 생각한 방법은

sum[r][c] = sum[r - 1][c] + r번째 행에서 1번 ~ c번값까지의 누적합 이었지만, 다른 사람들의 풀이를 보니

sum[r][c] = sum[r - 1][c] + sum[r][c - 1] - sum[r - 1][c - 1] + r번째 행에서 c번값

으로도 할 수 있고, 이게 더 쉬운 듯.

import sys

input = sys.stdin.readline

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

dp = [[0 for i in range(N + 1)] for j in range(N + 1)]

for r in range(1, N + 1):
    new_line = [0] + list(map(int, input().split()))
    accumalated_sum = 0
    for c in range(1, N + 1):
        accumalated_sum += new_line[c]
        dp[r][c] = dp[r - 1][c] + accumalated_sum

for _ in range(M):
    r1, c1, r2, c2 = map(int, input().split())
    answer = (
        dp[r2][c2] -
        dp[r1 - 1][c2] -
        (dp[r2][c1 - 1] - dp[r1 - 1][c1 - 1])
    )
    print(answer)

이 경우 시간복잡도는 O(N*2)이며 시간 내 통과가능!

dp는 정말 배울 게 많다는 점을 느끼게 해준 문제. 누적합 관련된 문제에서도 충분히 DP가 쓰일 수 있다. 또한 문제에 쓰일 재료(여기선 누적합들을 재료로 특정 구간의 합을 도출)를 만드는데에 DP방식이 쓰일 수 있음을 알게 됐다. 더욱 더 열심히 하자..