[백준 BOJ] 11660. 구간 합 구하기 5
22 Jul 2021난이도
Silver I
문제 풀이
N의 최대값이 1024이고 M의 최대값이 100000으로 주어져 있다. 시간제한이 1초이기에 좌표 2개가 주어질 때마다 구간에서 합을 구하려고 한다면, 당연하게도 시간초과가 난다. 따라서, 이 문제는 DP를 이용해 풀 필요가 있다. 먼저, 두 좌표가 주어졌을 때, 어떻게 하면 그 구간에서의 합을 구할 수 있을까?
단순히 생각해보면, 그냥 \(\small (x_1 \leq i \leq x_2, y_1 \leq j \leq y_2)\)을 만족하는 (i, j)에 대해 (i, j)에 있는 수를 모두 더하면 될 일이다. 그러나, 이런식으로 코드를 짜게 된다면 필연적으로 시간초과를 맞이하게 된다.
\(\small (x_2 - x_1) \times (y_2 - y_1) \leq O(N^2)\) 만큼의 연산이 주어진 좌표마다 수행되게 되니, \(\small O(M) \times O(N^2) = O(MN^2)\)이 되므로, 주어진 시간 내에 수행이 불가하다. 그럼, 저렇게 더하는 시간을 줄일 필요가 있는데.. 이를 해결하기 위해서 나는 (1, 1)에서 (x, y)까지의 합을 따로 저장하는 방법을 떠올렸다.
그렇게 따로 저장을 하면 우리가 구하고 싶은 영역인 D는 \(\small D = (all) - A - B + C\)로 구할 수 있게 된다. 문제에서 주어지는 점들을 빨간 점들로 표시해놨는데, 이 점들로부터 파란점들을 얻어내면 이런 방식으로 합을 구할 수 있게 된다. 이것을 수식으로 표현하면, \(\small S = sum(x_2, y_2) - sum(x_1 - 1, y_2) - sum(x_2, y_1 - 1) + sum(x_1 - 1, y_1 - 1)\)라고 쓸 수 있다. (이때, sum(x, y)는 (1,1)부터 (x, y)까지의 합)
그러면, sum에 해당하는 값들만 미리 구해놓으면 어떤 값이 들어오든 \(\small O(1)\)안에 해결할 수 있게 된다. \(\small dp[x][y]\)를 “(1, 1)에서 (x, y)까지의 합”으로 정의하자. 이 dp배열 값들을 미리 구하면 되는데, 이 값을 구할 때 무턱대고 반복문으로 합을 구해 저장하게 된다면, 위에서 \(\small O(MN^2)\)의 복잡도를 가지는 방법과 별반 다를게 없게 된다. 그렇기 때문에, 연산 횟수를 최대한 줄이기 위해 이전 합을 이용해서 다음 합을 구하면 좋을 듯 하다.
\[dp[1][2] = dp[1][1] + value[1][2]\] \[dp[1][3] = dp[1][2] + value[1][3]\]…
\[dp[3][2] = dp[3][1] + (value[1][2] + value[2][2] + value[3][2])\]…
처럼 쓸 수 있음을 생각해보면, dp점화식은 다음처럼 쓸 수 있다.
\[dp[x][y] = dp[x][y - 1] + \sum_{k = 1}^{x}value[k][y]\]
요런 점화식으로 값을 구한다면, 뒤의 Sum에 의해 연산횟수가 결정된다는 것을 알 수 있다. 이렇게 구하면 확실히 이전 방법보다는 연산횟수가 많이 줄어든다는 것을 알 수 있다. 이 점화식을 가지고 코드를 아래처럼 짤 수 있다.
for(int i = 0; i <= N; ++i) {
dp[i][0] = 0;
dp[0][i] = 0;
}
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= N; ++j) {
int summation = 0;
for(int n = 1; n <= i; ++n) {
summation += map[n][j];
}
dp[i][j] = dp[i][j - 1] + summation;
}
}
각각 x = 0, y = 0 이 되는 부분은 0으로 처리를 해주었고, 위의 식을 그대로 옮겨 dp배열의 값을 저장하도록 했다. 이후 \(\small S = sum(x_2, y_2) - sum(x_1 - 1, y_2) - sum(x_2, y_1 - 1) + sum(x_1 - 1, y_1 - 1)\) 이 식을 이용해 좌표가 들어올 때마다 정답을 출력하도록 코드를 짜면 끝이다. 물론 저 summation부분도 또 다른 dp로 최적화 해줄 수 있겠지만, 굳이 그러지 않아도 1초안에 해결된다.