BOJ 2167 2차원 배열의 합

yunjaeGong 2019. 7. 23. 21:54

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

2167번: 2차원 배열의 합

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

www.acmicpc.net

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

문제 풀기 교수님께서 말씀하셨던 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)까지의 누적합)

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

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

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

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