[C++] 백준 15724 - 주지수 [Silver1]

출처

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

처음엔 주지수라길래 무술 중에 하나인 주짓수인줄 알고 주짓수랑 알고리즘을 어떻게 연관지을까 궁금했지만 단순히 땅에 사는 사람들의 합을 구하는 문제였다..

풀이 전략

누적합을 구하는 문제이므로 처음에는 직접 구해야 하는 사각형의 범위를 지정해서 범위 내의 모든 cell값을 전부 더하는 방식을 시도했다. 하지만, 뒤에서 얘기하겠지만 이렇게 하게 될 경우 시간 초과 문제가 발생하기 때문에 DP를 활용해서 풀이할 것이다.

풀이

이 문제의 예시를 그려보면 위의 그림과 같다. DP로 누적합을 구하는 알고리즘의 경우 형태만 알아놓으면 정말 쉽게 풀 수 있다.

Main code를 보면,

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] + Map[i][j];
    }
}

이게 누적합을 구하는 알고리즘인데, 해석을 해보면 ...

DP[i-1][j] (윗칸) + DP[i][j-1] (왼쪽칸) - DP[i-1][j-1] (좌상단) + Map[i][j] (현위치의 값)

을 구하면 된다.

위의 식에서 좌상단의 값을 빼주는 이유는 옆칸과 윗칸의 DP 값을 더하게 되면 위의 사진에서 넓이가 2인 두 사각형을 더해주는 셈이 되는데 그렇게 될 경우 (i-1,j-1)위치가 중복으로 더해지는 문제가 생기기 때문에 중복을 방지하고자 더해주는 것이다.
그 후 현재 값을 더해주면 전체 사각형의 누적합이 (i,j) 위치에 저장되게 된다.

소스 코드

시간초과 ver.

/*
# Question: BJ 15724 (https://www.acmicpc.net/problem/15724)
# Rank : Silver1
# Algorithm : DP, Aggregate Sum
*/
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1025
using namespace std;

int N,M,K;
int Map[MAX][MAX];

void Input(){
    cin>>N>>M;
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            cin>>Map[i][j];
        }
    }
    cin>>K;
}

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

    Input();

    while(K--){
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;

        int result=0;
        for(int j=x1; j<=x2; j++){
            for(int k=y1; k<=y2; k++){
                result+=Map[j][k];
            }
        }
        cout<<result<<'\n';
    }
    return 0;
}

이 코드를 돌리면 분명 정답은 제대로 출력된다는 것을 알 수 있다. 그러나 DP와의 차이점은 DP의 경우 배열 전체의 누적합을 구해놓은 뒤, 입력 받은 범위 만큼을 구해주는 방법을 사용하지만 전체를 안구해놓고 범위 만큼을 직접 구하게 되면 위의 코드 처럼 while문 안에 이중 for문이 들어가게 되어 시간복잡도가 O(N^3)이 걸리게 되어 시간 초과가 발생하게 된다.

정답 Ver.

/*
# Question: BJ 15724 (https://www.acmicpc.net/problem/15724)
# Rank : Silver1
# Algorithm : DP, Aggregate Sum
*/
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1025
using namespace std;

typedef long long ll;

int N,M,K;
ll Map[MAX][MAX];
ll DP[MAX][MAX];

void Input(){
    cin>>N>>M;
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            cin>>Map[i][j];
        }
    }
    cin>>K;
}

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

    Input();
    // N*M 크기의 영역의 전체 누적합을 저장해놓음
    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] + Map[i][j];
        }
    }

    while(K--){
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;

 		// 구하고자 하는 영역의 누적합을 구함
        ll result = DP[x2][y2] - DP[x1-1][y2] - DP[x2][y1-1] + DP[x1-1][y1-1];
        cout<<result<<'\n';
    }
    return 0;
}

결과