[알고리즘 풀이 분석] BOJ 15724 주지수

오늘은 DP문제를 두 문제 풀어보았다!
첫번째 문제를 풀고 나서 감이 잘 잡히지 않아 연습할겸 조금 더 쉬운 문제로 BOJ 15724 주지수 를 풀어보았는데,, 흠,, 🤔 감을 잡았는가.. 모르겠다 ㅎ 더 연습해야지

BOJ 15724 주지수

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다.

진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다.

예를 들어, 위와 같이 사람이 살고 있다고 가정할 때 <그림 1>의 직사각형 범위의 사람 수를 알고 싶다면 진경대왕은 네 개의 정수 1 1 3 2를 부를 것이다. 마찬가지로 <그림 2>는 1 1 1 4, <그림 3>은 1 1 4 4가 될 것이다.

진경대왕을 위하여 이 참고 자료를 만들어내는 프로그램을 작성해보자.

입출력

나의 풀이

분명 DP 문제인데 왜 완전탐색처럼 생긴거니 이 문제??
단순히 떠오르는 방법으로는 뭐 어떻게 풀어도 O(N^2) 의 시간 복잡도를 피할 수 없을 것 같았다. (그치만 굳이굳이 해 보고 시간초과 확인함ㅋ,,)

DP 문제이기 때문에 값을 입력 받은 모든 값에 일일이 접근해서 뭔가 더하고, 그 값을 또 이용해서 더하고, 이런식으로 해결해야 시간초과를 피할 수 있을 것 같았다!

이 문제에서 dp[i][j] 에는 (1,1) 부터 (i,j)까지의 범위 내에 있는 사람들 수의 합이 적히게 된다! 그런데 이걸 어떻게 구하냐,, 하니,,

위에서, 그리고 옆에서 더해온 인구 합과 해당 칸에 입력되는 인구 수를 합하고 중복되는 값을 제외시켜 주는 방식이었다!

i=1, j=1

(1,1)에 거주하는 사람 수는 9명, 해당 칸 이전에 입력된 값이 없기에 dp[1][1] = 9 이다.

i=1, j=2

(1,2)에 거주하는 사람 수는 14명이고 해당 칸 보다 윗칸은 없고 왼쪽에서 누적된 인구는 9명이므로 dp[1][2] = 23 이다.

i=2, j=1

(2,1) 에 거주하는 사람은 1명이고 (1,1)부터 누적된 인구는 9명이므로 dp[2][1] = 10 이다.

i=2,j=2

그럼 (2,2)에 거주하는 사람은 31명이고 위아래로 누적된 인구합이 10명, 23명이니까 dp[2][2] = 10 + 23 + 31 = 64 일까?

Nope, 그렇지 않다!!

23은 dp[1][1] + 14 이고 10는 dp[1][1] + 1 이다. dp[1][1] 값이 두번 중복되어 들어가게 되는 것이다!

즉, dp[2][2] = dp[1][2] + dp[2][1] - dp[1][1] (현재까지의 인구 누적) + 31 ((2,2)에 거주하는 인원) = 55 가 올바른 값이다!

이와 같은 방식을 적용하면 점화식은
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + 해당 칸 인구 수
가 완성된다.

그럼 이렇게 2차원 dp 배열을 완성하고 난 뒤 (y1, x1) 부터 (y2, x2) 까지의 영역 내에 있는 인구 합은 어떻게 구할까?

완성된 dp 배열에서 (2,3) 부터 (4,4) 까지의 영역에 거주하는 인원을 구한다고 해보자,

구하고자 하는 영역은 연두색 네모로 칠해진 영역의 인구 합이고, 그 값은 전체 인구 합 중에서 노랑색 역역의 인구 합을 제외한 값이다.

그 영역 인구 합은 또 파란 영역의 인구 합과 붉은 영역의 인구를 합한 뒤 중복되어 집계되는 보라색 영역의 인구를 제외한 값이고

• 파란 영역의 인구 합 = dp[1][4]
• 붉은 영역의 인구 합 = dp[4][2]
• 보라색 영역의 인구 합 = dp[1][2]

이다.

결국, 진경대왕이 2,3,4,4 라고 외치면 우리는
dp[4][4] - dp[1][4] - dp[4][2] + dp[1][2] 값을 반환하면 되고, 점화식으로 나타내면,

dp[y2][x2] - dp[y2][x1] - dp[y1][x2] + dp[y1-1][x1-1] 임을 알 수 있다!!

코드

#include <iostream>
#include <vector>

// BOJ 15724 주지수, DP
using namespace std;

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

    int N, M, T;
    cin>>N>>M;

    vector<vector<int>> dp(N+1, vector<int>(M+1, 0));

    int people;
    // dp 배열 완성 
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cin>>people;
            dp[i][j] = people + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
        }
    }

    cin>>T;
    int y1, x1, y2, x2;
    
    for (int i = 0; i < T; ++i) {
        cin>>y1>>x1>>y2>>x2;
        // 주어진 영역의 인구 합 구하기 
        int ans = dp[y2][x2] - dp[y1-1][x2] - dp[y2][x1-1] + dp[y1-1][x1-1];
        cout<<ans<<'\n';
    }

    return 0;
}