[BOJ 5549 // C++] 행성 탐사

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 5549번 문제인 행성 탐사이다.
문제는 아래 링크를 확인하자.

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

5549번: 행성 탐사

1행1열부터 r행c열까지의 'J'의 개수를 \(dp[r][c]\)라 하자. r행c열에 적힌 문자가 'J'인 경우 \(dp[r][c] = dp[r-1][c] + dp[r][c-1] - dp[r-1][c-1] + 1\), 그렇지 않은 경우 \(dp[r][c] = dp[r-1][c] + dp[r][c-1] - dp[r-1][c-1]\)이 성립함을 이용하면 모든 \(dp[r][c]\)의 값을 \(O(RC)\)에 계산해낼 수 있다. 이는 'O' 및 'I'에 대해서도 마찬가지이다.

 

위와 점화식과 같은 원리의 식을 이용하면 위에서 구한 값들을 이용해 주어지는 쿼리의 답을 각 쿼리당 \(O(1)\)의 시간복잡도로 구해낼 수 있다. 이를 통해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int R, C, Q;
string board[1000];

int psumJ[1001][1001];
int psumO[1001][1001];
int psumI[1001][1001];

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

	cin >> R >> C >> Q;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			psumJ[r + 1][c + 1] = psumJ[r][c + 1] + psumJ[r + 1][c] - psumJ[r][c];
			psumO[r + 1][c + 1] = psumO[r][c + 1] + psumO[r + 1][c] - psumO[r][c];
			psumI[r + 1][c + 1] = psumI[r][c + 1] + psumI[r + 1][c] - psumI[r][c];

			if (board[r][c] == 'J') psumJ[r + 1][c + 1]++;
			else if (board[r][c] == 'O') psumO[r + 1][c + 1]++;
			else psumI[r + 1][c + 1]++;
		}
	}

	while (Q--) {
		int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
		cout << psumJ[r2][c2] - psumJ[r1 - 1][c2] - psumJ[r2][c1 - 1] + psumJ[r1 - 1][c1 - 1] << ' ';
		cout << psumO[r2][c2] - psumO[r1 - 1][c2] - psumO[r2][c1 - 1] + psumO[r1 - 1][c1 - 1] << ' ';
		cout << psumI[r2][c2] - psumI[r1 - 1][c2] - psumI[r2][c1 - 1] + psumI[r1 - 1][c1 - 1] << '\n';
	}
}