[파이썬, 자바] 백준 5549 : 행성탐사 (골드5)

[파이썬, 자바] 백준 5549 : 행성탐사 (골드5)

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

---

풀이

방향성 생각

• H,W가 각각 1000인 배열을 2차원 누적합 배열 3개를 만들어서 풀이
• 쿼리의 개수가 많기 떄문에 입출력 버퍼도 쓰기

 

---

파이썬

import sys
input = lambda : sys.stdin.readline().rstrip()

H,W = map(int,input().split())
TC = int(input())

arr = [list(input()) for _ in range(H)]
arr_info = [[[0]*(W+1) for _ in range(H+1)] for _ in range(3)]

cvt = {"J":0, "O":1, "I":2}
for i in range(H):
    for j in range(W):
        arr_info[cvt[arr[i][j]]][i+1][j+1] = 1

cumsum = [[[0]*(W+1) for _ in range(H+1)] for _ in range(3)]
for f in range(3):
    for i in range(1,H+1):
        for j in range(1,W+1):
            cumsum[f][i][j] = arr_info[f][i][j] + cumsum[f][i-1][j] + cumsum[f][i][j-1] - cumsum[f][i-1][j-1]

for _ in range(TC):
    y1,x1,y2,x2 = map(int,input().split())
    print(*[cumsum[f][y2][x2]-cumsum[f][y1-1][x2]-cumsum[f][y2][x1-1]+cumsum[f][y1-1][x1-1] for f in range(3)])

• arr -> 3차원으로 만들어서 각 층마다 J O I 정보 할당하기

자바

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int TC = Integer.parseInt(st.nextToken());

        char[][] arr = new char[H][W];
        for (int i=0; i<H; i++) {
            arr[i] = br.readLine().toCharArray();
        }

        int[][][] arrInfo = new int[3][H+1][W+1];
        for (int i=0; i<H; i++) {
            for (int j=0; j<W; j++) {
                int f = 0;
                if (arr[i][j] == 'O') {
                    f = 1;
                } else if (arr[i][j] == 'I') {
                    f = 2;
                }
                arrInfo[f][i+1][j+1] = 1;
            }
        }
        int[][][] cumsum = new int[3][H+1][W+1];
        for (int f=0; f<3; f++) {
            for (int i=1; i<=H; i++) {
                for (int j=1; j<=W; j++) {
                    cumsum[f][i][j] = cumsum[f][i-1][j] + cumsum[f][i][j-1] - cumsum[f][i-1][j-1] + arrInfo[f][i][j];
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int tc=0; tc<TC; tc++) {
            st = new StringTokenizer(br.readLine());
            int y1 = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());

            for (int f=0; f<3; f++) {
                sb.append(cumsum[f][y2][x2] - cumsum[f][y2][x1-1] - cumsum[f][y1-1][x2] + cumsum[f][y1-1][x1-1]).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb.toString());

    }
}

• 문자열 배열이 들어오므로 char[][]을 입력받고, line을 toCharArray로 변경하기.

---

코멘트

• .