BOJ 2167 2차원 배열의 합

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

2167번: 2차원 배열의 합

주말에 놀다 글 쓰는걸 잊어버려.. 저번 주에 

 

문제 풀기 교수님께서 말씀하셨던 dp 문제였다.

재귀식과 구현은 어렵지 않았지만, 중복 처리가 미흡해 한~참 헤맸다.

 

#include <cstdio>
int dp[301][301];
int main() {
    int N,M,K,i,j,x,y;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            scanf("%d",&dp[i][j]);
    // 누적합 계산
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            dp[i][j] += (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]);
        // dp[i-1][j-1]이 중복됨.

    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]);
        // 중복돼 빠진 dp[i-1][j-1]를 더해줌
        K--;
    }
}

dp[i][j]를 다음과 같이 정의하자

dp[i][j]: (i, j)까지의 누적 합 (단, i,는 y좌표)

 

(i,j)까지의 누적 합은 다음과 같이 구해진다.

(i-1,j), (i,j-1)까지 누적합의 합 - (i-1,j-1) (중복해서 더해진 (i-1,j-1)까지의 누적합)

따라서 누적합은 다음과 같이 구해진다.

코드에서 input은 dp[i][j]

x,y까지의 누적 합에서 i,j 바로 왼쪽 열, 윗행을 빼면 (i,j)에서 (x,y)까지의 누적 합 -(i-1,j-1)까지의 누적합이 된다.

(i,j 바로 왼쪽 열, 윗행을 빼는 과정에서 (i-1,j-1)까지 누적합이 두번 빠짐)

 

따라서 재귀식은 다음과 같다.