[백준] 5549. 행성 탐사

문제

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

풀이

누적합에 대한 문제이다. 처음 본 개념인데, dp (dynamic programming) 과 연결해서 생각할 수 있다. 누적합 자체가 어려운 개념은 아니고, 이전까지의 데이터의 합을 누적해서 저장하는 방식인데, 누적합과 이 문제에 대한 설명은 아래에서 참고하자. 여기서 설명을 할 수도 있지만, 해당 글들이 설명을 잘하기도 했고, 뭔가 특별한 알고리즘은 아니여서 따로 포스팅을 할 필요는 없다고 생각한다.

누적합이란? https://twpower.github.io/157-prefix-sum-basic-problem

문제 해설 https://uk-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80BOJ-5549%EB%B2%88-%ED%96%89%EC%84%B1%ED%83%90%EC%82%AC

#include <iostream>

using namespace std;

char map[1001][1001];
int sum_j[1001][1001] = { 0, }; 
int sum_o[1001][1001] = { 0, }; 
int sum_i[1001][1001] = { 0, };

int main(){

    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

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

    for(int i = 1; i <= M; i++){
        string s; cin >> s;
        for(int j = 0; j < N; j++){
            map[i][j + 1] = s[j];
        }
    }

    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            if(map[i][j] == 'J'){
                sum_j[i][j] = sum_j[i - 1][j] + sum_j[i][j - 1] - sum_j[i - 1][j - 1] + 1;
                sum_o[i][j] = sum_o[i - 1][j] + sum_o[i][j - 1] - sum_o[i - 1][j - 1];
                sum_i[i][j] = sum_i[i - 1][j] + sum_i[i][j - 1] - sum_i[i - 1][j - 1];
            }
            else if(map[i][j] == 'O'){
                sum_j[i][j] = sum_j[i - 1][j] + sum_j[i][j - 1] - sum_j[i - 1][j - 1];
                sum_o[i][j] = sum_o[i - 1][j] + sum_o[i][j - 1] - sum_o[i - 1][j - 1] + 1;
                sum_i[i][j] = sum_i[i - 1][j] + sum_i[i][j - 1] - sum_i[i - 1][j - 1];
            }
            else if(map[i][j] == 'I'){
                sum_j[i][j] = sum_j[i - 1][j] + sum_j[i][j - 1] - sum_j[i - 1][j - 1];
                sum_o[i][j] = sum_o[i - 1][j] + sum_o[i][j - 1] - sum_o[i - 1][j - 1];
                sum_i[i][j] = sum_i[i - 1][j] + sum_i[i][j - 1] - sum_i[i - 1][j - 1] + 1;
            }
        }
    }

    for(int i = 0; i < K; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        cout << sum_j[c][d] - sum_j[a - 1][d] - sum_j[c][b - 1] + sum_j[a - 1][b - 1] << ' ';
        cout << sum_o[c][d] - sum_o[a - 1][d] - sum_o[c][b - 1] + sum_o[a - 1][b - 1] << ' ';
        cout << sum_i[c][d] - sum_i[a - 1][d] - sum_i[c][b - 1] + sum_i[a - 1][b - 1] << '\n';
    }


    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/5549.cpp