[C++] BOJ 15724번 : 주지수

 

 

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

 

문제 3줄 요약

1. 네모 왕국의 1X1의 단위 구역을 여러 개 묶으려고 한다.

2. 4개의 숫자로 직사각형 범위를 알려준다.

3. 해당 직사각형 범위의 내에 살고 있는 사람 수를 구해보자.

 

---

 

DP가 아닌 완전 탐색으로 처음 접근했더니

시간 초과로 통과가 되지 않았다..!

 

직사각형의 시작 좌표와 (1,1)가

고정이 아니기에 DP 테이블을 사용할 수 있나? 에 대한

의문이 생겼다.

 

결국 코딩도사인 GPT에게

DP를 어느 부분에 적용하면 좋을지 도움을 받았다.

 

 

DP 테이블에 (1, 1)부터 해당 좌표까지의

직사각형 합을 저장(메모이제이션) 해두는 것이었다.

 

그 후

(1, 1) 부터 (x1, y1) 의 인원 수와

(1, 1) 부터 (x2, y2) 의 인원 수를 O(1)의 시간복잡도로 접근해

(x1, y1) 부터 (x2, y2) 범위 내의 인원을 구하는 것이다.

 

예를 들어 살펴보겠다.

 

 

그림 1의 직사각형 범위의

DP 테이블은 우측과 같이 채울 수 있겠다.

 

DP 테이블의 각 값은

(1, 1) 부터 해당 좌표(i, j) 까지의 인원 합을 나타낸다.

 

점화식은 다음과 같다.

 

DP[i][j] = 그림 1의 (i, j) 값 + DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1]

 

(i, j) 좌표의 좌측, 상단의 DP 값(인원의 합)을 더해주면 되는데

그럴 경우 좌측 대각선 상단 부분이 2번 더해지게 되므로

한 번을 빼주어 (1, 1) 부터 (i, j) 까지의 합을 구한다.

 

하지만 문제는

(1, 1) 부터 (x, y) 까지의 합이 아닌

(x1, y1) 부터 (x2, y2) 까지의 범위의 값이 궁금한거다.

 

이 DP 테이블을 어떻게 활용할 수 있을까?

 

---

 

 

빨간 직사각형 (1, 1) ~ (3, 2)

파란 직사각형 (1, 1) ~ (4, 4)를 이용하여

초록색 직사각형 (3, 2) ~ (4, 4) 범위 내에 인원을 구해보자.

 

전체 (1, 1) ~ (4, 4)에서

(1, 1) ~ (4, 1) 와 (1, 1) ~ (2, 4) 만큼 빼주고

2번 차감된 (1, 1) ~ (2, 1) 만큼 더해주면 된다.

 

 

 

DP 테이블의 값을 이용한다면?

테이블 안의 값이 DP 값으로 채워지진 않았다.

 

밝은색 좌표 3군데의 값을 활용하여

범위 (3, 2) ~ (4, 4) 값 = DP[4][4] - DP[4][1] - DP[2][4] + DP[2][2] 가 되겠다.

 

점화식으로 표현하면

answer = DP[x2][y2] - DP[x2][y1-1] - DP[x1-1][y2] + DP[x1-1][y-1];

 

위와 같이 작성할 수 있겠다.

 

따라서 코드는

아래와 같이 작성할 수 있다.

 

#include <iostream>
#include <vector>

using namespace std;

int jujisu[1025][1025];
int dp[1025][1025];

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int n, m;
    cin >> n >> m;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin >> jujisu[i][j];
            dp[i][j] = jujisu[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
        }
    }

    int k;
    cin >> k;

    for(int i=0; i<k; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] << "\n";
    }
    return 0;
}

 

---

DP 카테고리인 문제인줄 알고 풀었지만,

어디서 DP를 어떻게 활용해야할 지가 참 어려운 것 같다.