최신 글
10
제목 게시일
11

[백준] 11660번 : 구간 합 구하기 5

profile
코우
2021-05-17 21:07
조회 수 : 1992

출처 : 백준

문제 보러가기 : 구간 합 구하기5


해당 문제는 n x n의 2차원 배열에 각각의 1000보다 작거나 같은 자연수가 주어질 때 m개의 임의의 (x1,y1), (x2,y2)로 형성되는 사각형 내 포함되는 수들의 합을 구하는 문제이다.
이때  1 ≤ m ≤ 100,000이므로 (x1,y1), (x2,y2)내 인자들을 하나 하나 더하는 방법은 시간초과를 일으킬 수 밖에 없다.

따라서 별도의 n x n의 2차원 배열을 만들어 각각의 자리에 (1,1)부터 (i,j)까지의 합을 누적하여 저장한 후 (x1,y1), (x2,y2)를 입력받으면 누적합 배열에서 계산식을 통해 값을 바로 구하면 간단해지는 문제이다. 설명이 어려우니 그림을 한번 보자

reference

따라서 누적합 (i,j)구간을 구할 때는 sum[i][j] = a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]이라는 수식을 적용할 수 있다.
또한 n x n의 누적합 배열을 완성한 후 (x1,y1),(x2,y2)구간의 합을 구하는 경우 sum[x2][y2]-(sum[x2][y1-1]+sum[x1-1][y2])+sum[x1-1][y1-1]이라는 수식을 적용할 수 있다.

이처럼 다이나믹 프로그래밍을 이용하여 손쉽게 해당문제를 해결할 수 있다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n, m, x;
    int x1, x2, y1, y2;
    int sum[1025][1025];
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> x;
 
            sum[i][j] = x + sum[i - 1][j] + sum[i][j - 1- sum[i - 1][j - 1];
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
 
        cout << sum[x2][y2] - (sum[x1 - 1][y2] + sum[x2][y1 - 1]) + sum[x1 - 1][y1 - 1<< "\n";
    }
 
    return 0;
}
 
cs
share
twitter facebook kakao naver
댓글