[Baekjoon] 5549_행성 탐사

Gold V

문제(출처: https://www.acmicpc.net/problem/5549)

---

< 행성 탐사 >

 

문제 풀이 

 

만약 왼쪽 그림과 같이 입력이 들어온다면 오른쪽 그림과 같이 누적합을 구한다.

누적합을 구하는 방법은 [4 = 3+2-1+4번의 값]이다.

누적합을 구한 배열에서 빨간 박스 영역의 넓이를 구하는 방법은 [넓이 = 12-10-4+2]이다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _5549_ { // 행성 탐사
	static class Planet {
		private int j, o ,i;

		public Planet(int j, int o, int i) {
			this.j = j;
			this.o = o;
			this.i = i;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(bf.readLine());

		char arr[][] = new char[m + 1][n + 1];
		Planet result[][] = new Planet[m + 1][n + 1];

		for (int i = 0; i < m + 1; i++) {
			for (int j = 0; j < n + 1; j++) {
				result[i][j] = new Planet(0, 0, 0);
			}
		}

		for (int i = 1; i <= m; i++) {
			String str = bf.readLine();
			for (int j = 1; j <= n; j++) {
				arr[i][j] = str.charAt(j - 1);

				result[i][j].j = result[i - 1][j].j + result[i][j - 1].j - result[i - 1][j - 1].j;
				result[i][j].o = result[i - 1][j].o + result[i][j - 1].o - result[i - 1][j - 1].o;
				result[i][j].i = result[i - 1][j].i + result[i][j - 1].i - result[i - 1][j - 1].i;

				if (arr[i][j] == 'J') {
					result[i][j].j += 1;
				} else if (arr[i][j] == 'O') {
					result[i][j].o += 1;
				} else {
					result[i][j].i += 1;
				}
			}
		}

		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());

			Planet answer = new Planet(result[c][d].j, result[c][d].o, result[c][d].i);

			answer.i -= result[c][b-1].i;
			answer.j -= result[c][b-1].j;
			answer.o -= result[c][b-1].o;

			answer.i -= result[a-1][d].i;
			answer.j -= result[a-1][d].j;
			answer.o -= result[a-1][d].o;

			answer.i += result[a-1][b-1].i;
			answer.j += result[a-1][b-1].j;
			answer.o += result[a-1][b-1].o;

			bw.write(answer.j + " " + answer.o + " " + answer.i + "\n");
		}
		bw.flush();
	}
}

변수)
m, n : 지도의 크기
k : 조사 대상 영역의 개수
arr : 지도의 내용
result : 누적합
a, b, c, d : 조사 대상 영역의 정보
answer : 조사 대상 영역에 포함되어 있는 정글, 바다, 얼음 수
Planet : 정글, 바다, 얼음의 수를 가지는 행성

 

지도의 크기와 조사 대상 영역의 개수를 입력받는다. 누적합을 구하기 위해 result 배열의 값을 Planet으로 초기화한다. 지도의 내용을 입력받아 arr 배열에 저장하면서 누적합을 구한다. 

조사 대상 영역의 개수만큼 조사 대상 영역의 정보를 입력받는다. 위에서 설명한 공식대로 각 영역에 포함되어 있는 정글, 바다, 얼음의 수를 구해 출력한다.

---

---