10 May 2023

[Java] 백준 10836번: 여왕벌

10836

풀이 방법

이 문제는 힌트가 있다. 바로 모든 입력에서 이렇게 읽은 값들은 감소하지 않는 형태이다. 라는 것으로, 이를 다르게 해석하면 왼쪽 아래에서 시작해서 -> 왼쪽 상단 꼭지점을 거쳐 -> 오른쪽 상단을 갈 때 값이 줄어들지 않으므로 결국에는 최상단 행들의 값만 알면 된다는 것이다.

아래 그림으로 쉽게 표현해 보았다.

10836_2

이 때문에 최상단 행의 숫자들만 알게 되면 답을 빠르게 구할 수 있다.

하지만 한 가지 유의할 점이 있다. System.out.println으로 출력하면 83점이 나온다. 이는 시간 초과 때문으로, StringBuilder나 BufferedWriter를 사용하면 문제가 해결된다.

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_10836_여왕벌 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int m = Integer.parseInt(st.nextToken());
		int day = Integer.parseInt(st.nextToken());
		int[] space = new int[m*2-1];
		
		Arrays.fill(space, 1);
		
		for(int d=0; d<day; d++) {
			st = new StringTokenizer(br.readLine());
			int zero = Integer.parseInt(st.nextToken());
			int one = Integer.parseInt(st.nextToken());
			int two = Integer.parseInt(st.nextToken());

			for(int i=0; i<space.length; i++) {
				if(zero-- > 0) {
					continue;
				}
				else if(one-- > 0) {
					space[i]++;
				}
				else if(two-- > 0) {
					space[i] += 2;
				}
			}
			
		}
		
		for(int i=m-1; i>=0; i--) {
			sb.append(space[i]+" ");
			for(int j=m; j<space.length; j++) {
				sb.append(space[j]+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}

Thank You For Reading

점점 강해지고 있습니다.