[C++/BOJ] 5549 : 행성 탐사 (누적합) / 삽질 기록

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

문제

상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주 할 수 있는 구역의 지도를 만들어 지구로 보냈다.

상근이가 보내온 지도는 가로 Ncm, 세로 Mcm 직사각형 모양이다. 지도는 1cm 크기의 정사각형으로 나누어져 있고, 각 구역의 지형이 알파벳으로 표시되어 있다. 지형은 정글, 바다, 얼음 중 하나이며, 정글은 J, 바다는 O, 얼음은 I로 표시되어 있다.

지구에 있는 정인이는 조사 대상 영역을 K개 만들었다. 이때, 각 영역에 정글, 바다, 얼음이 각각 몇 개씩 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 크기 M과 N이 주어진다. (1 ≤ M, N ≤ 1000)

둘째 줄에 정인이가 만든 조사 대상 영역의 개수 K가 주어진다. (1 ≤ K ≤ 100000)

셋째 줄부터 M개 줄에는 상근이가 보낸 지도의 내용이 주어진다.

다음 K개 줄에는 조사 대상 영역의 정보가 주어진다. 정보는 네 정수 a b c d로 이루어져 있다. 구역은 직사각형 모양 이며, 왼쪽 위 모서리의 좌표가 (a, b) 오른쪽 아래 모서리의 좌표가 (c, d)이다.

출력

각 조사 대상 영역에 포함되어 있는 정글, 바다, 얼음의 수를 공백으로 구분해 한 줄에 한 정보씩 출력한다.

---

 

골드 5 누적합 문제

굉장한 노가다가 필요한 문제이다.

전체 풀이 코드는 맨 아래에 있음

 

풀다가 실수를 하나 했다.

 

            if(map[i][j]=='J') presum[i][j][0]=1;
            if(map[i][j]=='O') presum[i][j][1]=1;
            if(map[i][j]=='I') presum[i][j][2]=1;
            presum[i][j][0] += (presum[i-1][j][0]+presum[i][j-1][0]);
            presum[i][j][1] += (presum[i-1][j][1]+presum[i][j-1][1]);
            presum[i][j][2] += (presum[i-1][j][2]+presum[i][j-1][2]);

 

누적합을 구할 때

위처럼 [i-1][ ]과 [ ][j-1] 를 더해서 누적값을 구해주니까 presum[ ][ ][0] 을 출력했을 때 비정상적으로 큰 값이 나오는 것이다.

137? 이라니 내가 원한건 이게 아닌데

알고리즘을 잘못 짰다

J가 137개요,..??

생각해봤더니, 그냥 이전 값 두개를 더하면 안되고

[i-1][ ]과 [ ][j-1] 를 더해준 후 [i-1][j-1] 값을 빼줘야 내가 원하는 값이 나옴.

그래서 아래처럼 수정했더니 올바른 값이 나왔다!

 

            if(map[i][j]=='J') presum[i][j][0]=1;
            if(map[i][j]=='O') presum[i][j][1]=1;
            if(map[i][j]=='I') presum[i][j][2]=1;
            presum[i][j][0] += (presum[i-1][j][0]+presum[i][j-1][0]-presum[i-1][j-1][0]);
            presum[i][j][1] += (presum[i-1][j][1]+presum[i][j-1][1]-presum[i-1][j-1][1]);
            presum[i][j][2] += (presum[i-1][j][2]+presum[i][j-1][2]-presum[i-1][j-1][2]);

 

출력에도 주의가 필요하다.

일단 난 인덱스를 0부터 고려했으므로 실제 입력받은 좌표에서 값을 1씩 빼고 연산했다.

좀 이상한게.. 인덱스를 0부터 설정하니까 틀리고 1부터 연산되도록 수정하니까 맞았음. 왜지?

입력받고 1씩 빼는 연산이 시간초과가 되나.....흐음

 

쨌든 생각하기 귀찮으니 그냥 지도 입력 & presum 계산 시 인덱스를 1부터 고려하면 됨.

 

입력값이 3, 5, 4, 7 이라고 가정할 때 범위가 아래 표의 빨간 부분과 같으므로

전체 표에서 (4,4)까지의 영역과 (2,7)까지의 영역을 빼줘야 한다. 

 

먼저 (4,4)를 빼면 아래의 노란 부분을 지우는 셈이다

 

인덱스	1	2	3	4	5	6	7
1	(1,1)	(1,2)	(1,3)	(1,4)	(1,5)	(1,6)	(1,7)
2	(2,1)	(2,2)	(2,3)	(2,4)	(2,5)	(2,6)	(2,7)
3	(3,1)	(3,2)	(3,3)	(3,4)	(3,5)	(3,6)	(3,7)
4	(4,1)	(4,2)	(4,3)	(4,4)	(4,5)	(4,6)	(4,7)

 

그리고 (2,7)을 빼면 아래의 파란 부분 영역을 지우는 셈이다.

인덱스	1	2	3	4	5	6	7
1	(1,1)	(1,2)	(1,3)	(1,4)	(1,5)	(1,6)	(1,7)
2	(2,1)	(2,2)	(2,3)	(2,4)	(2,5)	(2,6)	(2,7)
3	(3,1)	(3,2)	(3,3)	(3,4)	(3,5)	(3,6)	(3,7)
4	(4,1)	(4,2)	(4,3)	(4,4)	(4,5)	(4,6)	(4,7)

 

근데 그러면 아래의 연두색 영역이 2번 빠지게 되므로, 이 영역을 다시 한번 더 더해줘야 한다.

인덱스	1	2	3	4	5	6	7
1	(1,1)	(1,2)	(1,3)	(1,4)	(1,5)	(1,6)	(1,7)
2	(2,1)	(2,2)	(2,3)	(2,4)	(2,5)	(2,6)	(2,7)
3	(3,1)	(3,2)	(3,3)	(3,4)	(3,5)	(3,6)	(3,7)
4	(4,1)	(4,2)	(4,3)	(4,4)	(4,5)	(4,6)	(4,7)

 

그러면 아래와 같은 출력 연산을 도출할 수 있다.

 

cout << presum[c][d][0] - presum[a - 1][d][0] - presum[c][b - 1][0] + presum[a - 1][b - 1][0] << " ";
cout << presum[c][d][1] - presum[a-1][d][1] - presum[c][b-1][1] + presum[a-1][b-1][1] << " ";
cout << presum[c][d][2] - presum[a-1][d][2] - presum[c][b-1][2] + presum[a-1][b-1][2]<< '\n';

 

 

 

나의 풀이

#include <iostream>
#include <string>
using namespace std;

string mapinput;
char map[1001][1001];
int ks[4] = {0};
int presum[1001][1001][3]={0};
int m;
int n;
int k;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int a;
    int b;
    int c;
    int d;

    cin >> m >> n >> k;
    for (int i = 1; i <= m;++i){
        cin >> mapinput;
        for (int j = 1; j <= n; ++j){
            map[i][j] = mapinput[j-1];
        }
    }
    // 정글은 J, 바다는 O, 얼음은 I, 갯수 미리 구해놓기
    // 세로 1열 먼저 채우기
    for (int i = 1; i <= m;++i){
        if(map[i][1]=='J') presum[i][1][0]=1;
        else if(map[i][1]=='O') presum[i][1][1]=1;
        else if(map[i][1]=='I') presum[i][1][2]=1;
        presum[i][1][0] += presum[i-1][1][0];
        presum[i][1][1] += presum[i-1][1][1];
        presum[i][1][2] += presum[i-1][1][2];
    }
    // 가로 1열 먼저 채우기
    for (int i = 2; i <= n;++i){
        if(map[1][i]=='J') presum[1][i][0]=1;
        else if(map[1][i]=='O') presum[1][i][1]=1;
        else if(map[1][i]=='I') presum[1][i][2]=1;
        presum[1][i][0] += presum[1][i-1][0];
        presum[1][i][1] += presum[1][i-1][1];
        presum[1][i][2] += presum[1][i-1][2];
    }
    // 나머지 채우기
    for (int i = 2; i <= m;++i){
        for (int j = 2; j <= n;++j){
            presum[i][j][0] += (presum[i-1][j][0]+presum[i][j-1][0]-presum[i-1][j-1][0]);
            presum[i][j][1] += (presum[i-1][j][1]+presum[i][j-1][1]-presum[i-1][j-1][1]);
            presum[i][j][2] += (presum[i-1][j][2]+presum[i][j-1][2]-presum[i-1][j-1][2]);
            if(map[i][j]=='J') presum[i][j][0]+=1;
            else if(map[i][j]=='O') presum[i][j][1]+=1;
            else if(map[i][j]=='I') presum[i][j][2]+=1;
        }
    }

    for (int i = 0; i < k; ++i){
        cin >> a >> b >> c >> d;
        int jungle = presum[c][d][0] - presum[a - 1][d][0] - presum[c][b - 1][0] + presum[a - 1][b - 1][0];
        int ocean = presum[c][d][1] - presum[a - 1][d][1] - presum[c][b - 1][1] + presum[a - 1][b - 1][1];
        int ice = presum[c][d][2] - presum[a - 1][d][2] - presum[c][b - 1][2] + presum[a - 1][b - 1][2];
        cout << jungle << ' ' << ocean << ' ' << ice << '\n';
    }
}