백준5549 - 행성 탐사

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

5549번: 행성 탐사

처음에 bfs로 풀었다가 시간초과나서 dp로 푼 문제이다. 문제에서 시작하는 점과 끝나는 점을 주었고 오른쪽과 아래로만 이동하면서 풀면 되는 문제이기 때문에 굳이 bfs로 풀지 않고 dp로 해결할 수가 있었다. 구간합을 이용하여 풀었다.

 

앞으로 두 방향으로 이동하게 정해준 면적 구하기 문제는 dp로 해결해야겠다.

 

#include <iostream>
using namespace std;

char mat[1001][1001];
int cntJ[1001][1001] = { 0, };
int cntO[1001][1001] = { 0, };
int cntI[1001][1001] = { 0, };
int n, m, o;
int a, b, c, d;

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

	cin >> n >> m;
	cin >> o;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
			if (mat[i][j] == 'J') { //1,1에서 시작하여 현재 i, j까지 직사각형 모양으로 존재하는 J의 갯수
				cntJ[i][j] = cntJ[i - 1][j] + cntJ[i][j - 1] - cntJ[i - 1][j - 1] + 1;
				cntO[i][j] = cntO[i - 1][j] + cntO[i][j - 1] - cntO[i - 1][j - 1];
				cntI[i][j] = cntI[i - 1][j] + cntI[i][j - 1] - cntI[i - 1][j - 1];
			}
			else if (mat[i][j] == 'O') { //1,1에서 시작하여 현재 i, j까지 직사각형 모양으로 존재하는 O의 갯수
				cntJ[i][j] = cntJ[i - 1][j] + cntJ[i][j - 1] - cntJ[i - 1][j - 1];
				cntO[i][j] = cntO[i - 1][j] + cntO[i][j - 1] - cntO[i - 1][j - 1] + 1;
				cntI[i][j] = cntI[i - 1][j] + cntI[i][j - 1] - cntI[i - 1][j - 1];
			}
			else { //1,1에서 시작하여 현재 i, j까지 직사각형 모양으로 존재하는 I의 갯수
				cntJ[i][j] = cntJ[i - 1][j] + cntJ[i][j - 1] - cntJ[i - 1][j - 1];
				cntO[i][j] = cntO[i - 1][j] + cntO[i][j - 1] - cntO[i - 1][j - 1];
				cntI[i][j] = cntI[i - 1][j] + cntI[i][j - 1] - cntI[i - 1][j - 1] + 1;
			}
		}
	}

	//구간합으로 구한 결과중 1, 1에서 n, m까지의 결과를 4부분으로 나누어 답을 구한다.
	for (int i = 0; i < o; i++) {
		cin >> a >> b >> c >> d;
		cout << cntJ[c][d] - cntJ[c][b - 1] - cntJ[a - 1][d] + cntJ[a - 1][b - 1] << ' ';
		cout << cntO[c][d] - cntO[c][b - 1] - cntO[a - 1][d] + cntO[a - 1][b - 1] << ' ';
		cout << cntI[c][d] - cntI[c][b - 1] - cntI[a - 1][d] + cntI[a - 1][b - 1] << '\n';
	}
}