[BOJ-11660][C++] 구간 합 구하기 5

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

 

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

 

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

 

예제 입력 1

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

 

예제 출력 1

27
6
64

 

예제 입력 2

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

 

예제 출력 2

1
2
3
4

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 누적 합

 

문제 출처

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

11660번: 구간 합 구하기 5

 

---

 

문제 해결 방법

• 2차원 배열 부분 합 알고리즘을 이용하여 풀 수 있었던 문제였다.
• 2차원 배열 부분 합 알고리즘은 1차원 배열 부분 합 알고리즘보다 더 복잡하다.

 

2차원 배열 부분 합 알고리즘

• 우선 2차원 배열 부분 합 알고리즘은 다음과 같다.

// N X M 배열에서 부분 합 구하기
for (int r = 1; r <= N; r++) {
    for (int c = 1; c <= M; c++) {
        cin >> matrix[r][c];
        
        pSum[r][c] = pSum[r - 1][c] + pSum[r][c - 1] - pSum[r - 1][c - 1] + matrix[r][c];
    }
}

// 부분 합을 구할 영역 : (x1, y1), (x2, y2)
cout << pSum[x2][y2] - (pSum[x1 - 1][y2] + pSum[x2][y1 - 1]) + pSum[x1 - 1][y1 - 1] << '\n';

 

문제 해결을 위한 알고리즘 원리 이해하기

• 문제 해결을 위한 알고리즘 원리를 이해해보자.
• 다음과 같이 4×4 크기의 2차원 배열(@matrix@)에 @예제 입력 1@의 값들이 들어 있다. (@r@ :행(Row), @c@ : 열(Column)) 

r \ c	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	3	4	5
3	0	3	4	5	6
4	0	4	5	6	7

 

• 부분 합 배열(@pSum@)을 다음과 같이 만들어주고, @pSum[a][b]@를 (1, 1)에서 (a, b)까지의 영역의 넓이의 부분 합이라고 하자. 그러면 다음과 같이 부분 합 배열을 채울 수  있다.

r \ c	0	1	2	3	4
0	0	0	0	0	0
1	0	1	3	6	10
2	0	3	8	15	24
3	0	6	15	27	42
4	0	10	24	42	64

 

• 다음과 같이 2차원 배열 @matrix@가 있을 때, 부분 합 배열(@pSum@)을 채워나가보자.

r \ c	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	3	4	5
3	0	3	4	5	6
4	0	4	5	6	7

 

• pSum[1][2] ~ pSum[1][4], pSum[2][1] ~ pSum[4][1] 부분은 1차원 배열의 부분 합을 구하는 과정과 비슷하다.

r \ c	0	1	2	3	4
0	0	0	0	0	0
1	0	1	3	6	10
2	0	3	?
3	0	6
4	0	10

 

• pSum[2][2]는 (1, 1)부터 (2, 2)까지의 영역의 넓이를 의미한다. 다음의 과정을 통해 구할 수 있다.

pSum[2][2]
= pSum[1][2] + pSum[2][1] - pSum[1][1](중복 되는 부분) + matrix[2][2]
= 3 + 3 - 1 + 3
= 8

r \ c	0	1	2	3	4
0	0	0	0	0	0
1	0	1	3	6	10
2	0	3	8
3	0	6
4	0	10

 

• 이 과정을 일반화하여 부분 합 배열을 채워나가는 식을 완성해보자.

pSum[r][c]
= pSum[r - 1][c] + pSum[r][c - 1] + pSum[r - 1][c - 1] + matrix[r][c]

 

• 코드로 표현하면 다음과 같다.

pSum[r][c] = pSum[r - 1][c] + pSum[r][c - 1] - pSum[r - 1][c - 1] + matrix[r][c];

 

• (2, 2)에서 (4, 4)까지의 넓이를 구해보자.

r \ c	0	1	2	3	4
0	0	0	0	0	0
1	0	1	3	6	10
2	0	3	8	15	24
3	0	6	15	27	42
4	0	10	24	42	64

• (2, 2)에서 (4, 4)까지의 넓이는 pSum[4][4] - (pSum[4][1] + pSum[1][4]) + pSum[1][1]이다. 

 

• (1, 2)에서 (3, 4)까지의 넓이를 구해보자.

r \ c	0	1	2	3	4
0	0	0	0	0	0
1	0	1	3	6	10
2	0	3	8	15	24
3	0	6	15	27	42
4	0	10	24	42	64

• (1, 2)에서 (3, 4)까지의 넓이는 pSum[3][4] - (pSum[3][1] + pSum[0][4]) + pSum[0][1]이다. 

 

• 일반화 해보자. (a, b)에서 (c, d) 까지의 넓이를 구하면 다음과 같다.

pSum[c][d] - (pSum[a - 1][d] + pSum[c][b - 1]) + pSum[a - 1][b - 1]

• (a, b)와 (c, d)를 각각 (x1, y1)과 (x2, y2)로 바꾸면 다음과 같다.

pSum[x2][y2] - (pSum[x1 - 1][y2] + pSum[x2][y1 - 1]) + pSum[x1 - 1][y1 - 1]

• 코드로 표현하면 다음과 같다.

pSum[x2][y2] - (pSum[x1 - 1][y2] + pSum[x2][y1 - 1]) + pSum[x1 - 1][y1 - 1]

 

코드

#include <iostream>
using namespace std;

int N, M;
int matrix[1025][1025];
int pSum[1025][1025];
int x1, x2, y1, y2; 

void Solution() {
    cin >> N >> M;

    // 표 채우기
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            cin >> matrix[r][c];
            pSum[r][c] = pSum[r - 1][c] + pSum[r][c - 1] - pSum[r - 1][c - 1] + matrix[r][c];
        }
    }

    // 구해야 하는 좌표 입력 받기 : (x1, y1), (x2, y2)
    for (int i = 1; i <= M; i++) {
        cin >> x1 >> y1 >> x2 >> y2;

        cout << pSum[x2][y2] - (pSum[x1 - 1][y2] + pSum[x2][y1 - 1]) + pSum[x1 - 1][y1 - 1] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Solution();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [누적 합]
• 실버I

 

2차원 배열에서 누적 합(부분 합) 구하기

알고리즘

void PrefixSum2DArray() {
    cin >> N >> M;

    // 표 채우기 (N x M)
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= M; c++) {
            cin >> matrix[r][c];
            pSum[r][c] = pSum[r - 1][c] + pSum[r][c - 1] - pSum[r - 1][c - 1] + matrix[r][c];
        }
    }

    cin >> K;

    // 구해야 하는 좌표 입력 받기 : (x1, y1), (x2, y2)
    for (int i = 1; i <= K; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        
        cout << pSum[x2][y2] - (pSum[x1 - 1][y2] + pSum[x2][y1 - 1]) + pSum[x1 - 1][y1 - 1] << '\n';
    }
}

 

관련 문제

• https://dev-astra.tistory.com/332

[BOJ-2167][C++] 2차원 배열의 합