백준 5549번 행성 탐사

🔒[문제 url]

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

🔑알고리즘

삼차원 배열을 선언하여, J O I 각각의 지도에 대해 이차원 누적합을 구한다.

• prefixSum[0][[i][j] : (1,1)부터 (i,j)까지 J의 누적합
• prefixSum[1][i][j] : (1,1)부터 (i,j)까지 O의 누적합
• prefixSum[2][[i][j] : (1,1)부터 (i,j)까지 I의 누적합
  
  
• (1,1)부터 (x,y)까지의 누적합은 어떻게 구하는가?

prefixSum[area][x][y] =
    prefixSum[area][x-1][y] 
    + prefixSum[area][x][y-1] 
    - prefixSum[area][x-1][y-1]

• (a,b)부터 (c,d)까지의 누적합은 어떻게 구하는가?
  

prefixSum[area][c][d]
- prefixSum[area][c][b-1]
- prefixSum[area][a-1][d]
+ prefixSum[area][a-1][b-1]

• 본 문제는 cin과 scanf , cout과 printf의 입출력 속도 차이로 인해 AC 결정 여부를 달리한다. 더 빠른 scanf printf를 이용하자.
  • 참고 : 입력 속도 비교 , 출력 속도 비교

🐾부분 코드

void INPUT()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%1s",&map[i][j]);

            //누적합
            for(int area = 0; area < 3; area++)
            {
                prefixSum[area][i][j] =
                        prefixSum[area][i-1][j] + prefixSum[area][i][j-1] - prefixSum[area][i-1][j-1];
                if(area == 0 && map[i][j] == 'J') prefixSum[area][i][j]++;
                else if(area == 1 && map[i][j] == 'O') prefixSum[area][i][j]++;
                else if(area == 2 && map[i][j] == 'I') prefixSum[area][i][j]++;
            }
        }
}

<입력 및 누적합 구하기>
각 지형에 따른 누적합을 따로 구한다.

🪄전체 코드

#include <iostream>
using namespace std;

int n,m;
char map[1001][1001];
int k;
int a,b,c,d;

int prefixSum[3][1001][1001];// J O I

void INPUT()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%1s",&map[i][j]);

            //누적합
            for(int area = 0; area < 3; area++)
            {
                prefixSum[area][i][j] =
                        prefixSum[area][i-1][j] + prefixSum[area][i][j-1] - prefixSum[area][i-1][j-1];
                if(area == 0 && map[i][j] == 'J') prefixSum[area][i][j]++;
                else if(area == 1 && map[i][j] == 'O') prefixSum[area][i][j]++;
                else if(area == 2 && map[i][j] == 'I') prefixSum[area][i][j]++;
            }
        }
}


void SOLVE()
{

    while(k--)
    {
        scanf("%d %d %d %d",&a,&b,&c,&d);

        for(int area = 0; area < 3; area++)
        {
            printf("%d ", prefixSum[area][c][d]
                    - prefixSum[area][c][b-1]
                    - prefixSum[area][a-1][d]
                    + prefixSum[area][a-1][b-1]);
        }
        printf("\n");
    }

}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

누적합.... 재미없....다......