[BOJ 5549] 행성 탐사

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

5549번: 행성 탐사

 

- 문제 요약

 

첫째 줄에 정수 M과 N이 입력으로 들어온다. (1<=M,N<=1,000)

그 다음 줄에 조사 대상 영역의 개수를 나타내는 정수 K가 입력된다. (1<=K<=100,000)

세 번째 줄부터 J(정글), O(바다), I(얼음)으로만 구성된 M*N 크기의 맵이 입력으로 들어온다.

다음 K개의 줄에는 정수 a,b,c,d가 입력으로 들어오는데, 이는 직사각형 형태의 조사 대상 영역의 왼쪽 위 모서리 좌표 (a,b)와 오른쪽 아래 모서리 좌표 (c,d)를 뜻한다.

각 영역별로 정글, 바다, 얼음이 몇 개 포함되어 있는지 출력하시오.

 

 

- 알고리즘 정리

 

 DP로 구간합을 구해서 풀어줬습니다.

현재 인덱스의 값이 정글인지 바다인지 얼음인지에 따라 케이스를 나눠서 구간합 처리를 해줬습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1001
int m,n,k,J[MAX][MAX],O[MAX][MAX],I[MAX][MAX];
char arr[MAX][MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>m>>n>>k;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>arr[i][j];
			if(arr[i][j]=='J'){
				J[i][j]=J[i-1][j]+J[i][j-1]-J[i-1][j-1]+1;
				O[i][j]=O[i-1][j]+O[i][j-1]-O[i-1][j-1];
				I[i][j]=I[i-1][j]+I[i][j-1]-I[i-1][j-1];
			}
			else if(arr[i][j]=='O'){
				J[i][j]=J[i-1][j]+J[i][j-1]-J[i-1][j-1];
				O[i][j]=O[i-1][j]+O[i][j-1]-O[i-1][j-1]+1;
				I[i][j]=I[i-1][j]+I[i][j-1]-I[i-1][j-1];
			}
			else{
				J[i][j]=J[i-1][j]+J[i][j-1]-J[i-1][j-1];
				O[i][j]=O[i-1][j]+O[i][j-1]-O[i-1][j-1];
				I[i][j]=I[i-1][j]+I[i][j-1]-I[i-1][j-1]+1;
			}
		}
	} // input 
	for(int i=0;i<k;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		cout<<J[c][d]-J[c][b-1]-J[a-1][d]+J[a-1][b-1]<<" ";
		cout<<O[c][d]-O[c][b-1]-O[a-1][d]+O[a-1][b-1]<<" ";
		cout<<I[c][d]-I[c][b-1]-I[a-1][d]+I[a-1][b-1]<<"\n";		
	}
}

코드 제출 결과