[백준 5549번] 행성 탐사 (C++)

문제링크 : https://www.acmicpc.net/problem/5549

5549번: 행성 탐사

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int area[1001][1001][3]; //M, N, 정글 : J, 바다 : O, 얼음 : I
int result[1001][1001][3];
char ch; 

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int M, N, K;
    cin >> M >> N >> K;

    for(int i=1; i<=M; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin >> ch;
            if(ch == 'J') area[i][j][0]++; //해당위치에 J 카운트
            else if (ch == 'O') area[i][j][1]++; //해당위치에 O 카운트
            else if (ch == 'I') area[i][j][2]++; //해당위치에 I 카운트

            for(int k=0; k<3; k++)
            {
                result[i][j][k] = area[i][j][k] + result[i-1][j][k] + result[i][j-1][k] - result[i-1][j-1][k]; //자기 자신 + 오는 경우 2가지 - 중복값
            }
        }
    }

    while(K--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        for(int i=0; i<3; i++)
        {
            cout << result[c][d][i] - result[a-1][d][i] - result[c][b-1][i] + result[a-1][b-1][i] << " "; //필요없는 구역 자르고 중복된 값만큼 다시 더해주기
        }
        cout <<'\n';
    }

    return 0;
}

먼저 문자는 J, O, I 이렇게 3가지 이므로 3차원배열을 사용한다.

각각에 문자열에 대해 J일때는 [0]의 값을, O일때는 [1]의 값을, I일때는 [2]의 값을 증가시켜준다.

이후 더해준 값들을 저장할 배열에 각 케이스에 대해 값들을 저장해준다.

값을 저장하는 케이스는 일단 자기 자신, 왼쪽에서 온 값, 오른쪽에서 온 값 이렇게 3가지를 더해준다.

그런데 이러면 중복값이 존재하여 대각선 위의 값만큼 빼주어야 한다.

아래 예제를 보자

 

OIO
IOJ

I의 갯수

[1][1] = 0
[1][2] = 1 (자기 자신)
[1][3] = 1 (왼쪽에서 온 값)

[2][1] = 1 (자기 자신)
[2][2] = 2 (왼쪽 + 위)
[3][2] = 3 (왼쪽 + 위) <중복발생>
왼쪽 대각선위의 값이 아래로 1번 옆으로 1번 이동하여 중복되었으므로 해당 값만큼 빼줌

 

반대로 출력할때를 보면 필요없는 구역을 잘라야 한다.

이때 왼쪽 범위와 아래쪽 범위를 자르게 되는데 위에서와 마찬가지로 중복이 발생하여 이번엔 빼준 경우이므로 중복값을 더해줘야 한다.