[백준/5549] 행성 탐사 - JAVA

📌 문제

알고리즘 분류 : 누적합
난이도 : 골드5
출처 : 백준 - 행성 탐사

🦧 문제 풀이 접근

좌표값과 J,I,O 정보를 담는 3차원 배열 선언.

J->0, O->1, I->2

0,0부터 각 좌표값까지의 J,O,I 정보를 누적.
누적된 값의 차를 통해 (a,b)와 (c,d) 범위의 J, O, I 값 계산.

(c,d) - (a-1,d) - (c,b-1) + (a-1,b-1)

💻 code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());
        int[][][] planets = new int[M+1][N+1][3];//0 -> J, 1 -> O, 2-> I
        for(int i=1;i<=M;i++) {
            String line = br.readLine();
            for(int j=1;j<=N;j++) {
                for(int k=0;k<3;k++) {
                    planets[i][j][k] = planets[i][j-1][k] + planets[i-1][j][k] - planets[i-1][j-1][k];
                }
                switch (line.charAt(j-1)) {
                    case 'J' :
                        planets[i][j][0]++;
                        break;
                    case 'O' :
                        planets[i][j][1]++;
                        break;
                    case 'I' :
                        planets[i][j][2]++;
                        break;
                }
            }
        }
        for(int i=0;i<K;i++) {
            st = new StringTokenizer(br.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());
            for(int j=0;j<3;j++) {
                sb.append(planets[c][d][j] - planets[a-1][d][j] - planets[c][b-1][j] + planets[a-1][b-1][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

🥇 결과

🎓 느낀점

자주 나오는 누적합 유형이었으나 3차원 배열을 사용하는 점에서 색다른 문제였다.