[BOJ] 2167. 2차원 배열의 합(DP, 누적합).py.cpp

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

최대 배열의 크기는 300x300 = 900,000 이고,

쿼리는 10,000개이므로 i,j 부터 x,y 까지 하나씩 더하면서 합을 구하려면

최대 900,000의 연산이 필요할 것이다.

배열의 크기가 900,000이고 쿼리가 10,000이 입력으로 주어진다면

9,000,000,000번의 연산이 필요하다.

그렇기때문에 누적합을 구하여 풀어야 한다.

먼저 일차원배열의 누적합은 DP[i] = i까지의 합이라고 했을 때,

i~j까지의 합을 

1

DP[j] - DP[i-1]

cs

 로 구할 수 있다. 

하지만, 이차원배열은 좀 다르다.

위에서 구한 누적합 + 왼쪽에서 구한 누적합 - 교집합으로 구할 수 있다.

1

DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]

cs

input()이 아래 그림과 같다면

(왼쪽에서 구한 누적합) + (위쪽에서 구한 누적합) - (교집합)의 결과는 아래와 같다

처음에 (2,1)이 왜 9가 되는지 이해가 가질 않았었는데,

(1,1)부터 (2,1)까지의 합인 1+2+4+8=15가 되는게 아닌가? 생각했었다.

그러나! 

(1,1)부터 (2,1)까지의 부분 합은 아래 그림과 같다.

본론으로,

여기서 (1,3)부터 (2,3)까지의 합을 구하는 공식에 

DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1] 를 적용해보면

(왼쪽에서 구한 누적합) + (위쪽에서 구한 누적합) - (교집합)

27+ 7 - 3 + 32 = 63 이 되는 것을 볼 수 있다.

그 다음이 중요하다.

문제에서처럼

i, j, x, y 가 1 3 2 3 으로 입력되었을 때,

(1,3)부터 (2,3)까지의 부분합을 구해야 한다.

즉, 아래 그림 영역과 같은데

이 부분을 구하기 위해서는 누적합을 구했던 방식과 유사하다.

(x,y) 까지의 누적합에서

(i, j) (x,y) 범위 주위를 둘러싼 누적합을 빼주고 교집합을 더해주면 된다.

이를 식으로 표현해보면 (2,3) - (2,2) - (0,3) + (0,2) 가 된다.

즉, i, j, x, y 가 1 3 2 3 으로 입력되었을 때,

DP[x][y] - DP[x][j-1] - DP[i-1][y] + DP[i-1][j-1] 이 된다.

그래서 63 - 27 - 0 + 0 = 36이 결과로 출력된다.

정리하면 아래와 같다.

# 이차원 배열의 (1,1)부터 (i,j)까지의 누적합 구하기
DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]
 
# (i,j)부터 (x,y)까지의 부분합 구하기
DP[x][y] - DP[x][j-1] - DP[i-1][y] + DP[i-1][j-1]

#. Python Code

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
DP = [[0 for i in range(0, M+1)] for _ in range(N+1)]
 
for i in range(1, N+1):
    for j in range(1, M+1):
        DP[i][j] = DP[i][j-1] + DP[i-1][j] - DP[i-1][j-1] + A[i-1][j-1]
 
for _ in range(int(input())):
    i, j, x, y = map(int, input().split())
    print(DP[x][y] - DP[x][j-1] - DP[i-1][y] + DP[i-1][j-1])

line 3) 영역 밖을 0으로 채워주면 index 접근관련 에러가 발생할 확률이 줄어들어서 편리해진다.

line 7) (1,1)부터 (i,j)까지의 누적합을 구하는 공식(?)이다. 자세한 설명은 풀이 참고.

line 11) (i,j)부터 (x,y)까지의 누적합을 구하는 공식. 자세한 설명은 풀이 참고.

#. Cpp Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int A[301][301], DP[301][301];
 
int main(void)
{
    int N, M, i, j;
    freopen("input.txt", "rt", stdin);
    scanf("%d %d", &N, &M);
 
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= M; j++) {
            scanf("%d", &A[i][j]);
        }
    }
 
    // (1,1)부터 (i,j)까지의 누적합
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= M; j++) {
            DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP [i - 1][j - 1] + A[i][j];
        }
    }
 
    int K, x, y;
    scanf("%d", &K);
    while (K--) {
        scanf("%d %d %d %d", &i, &j, &x, &y);
        printf("%d\n", DP[x][y] - DP[x][j - 1] - DP[i - 1][y] + DP[i - 1][j - 1]);
    }
 
    return 0;
}