[백준 - Java] 10836번 : 여왕벌

문제

www.acmicpc.net/problem/10836

설명

매일매일 애벌레를 키우면 무조건 시간 초과가 난다!!

1,000,000 최대 백만일까지 애벌레를 키울 수 있기 때문!!

 

잘 생각해보면 매일 애벌레를 키워할 필요가 없다!

 

제일 왼쪽 열과 제일 위쪽 행의 애벌레만 주어지는 N날 동안 주어지는 0, 1, 2로 키우고,

나머지 (1, 1) ~ (M, M) 애벌레들은 N날이 지난 후, 

문제의 조건 2에 따라 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들 중 가장 큰 사이즈로 키워진 애벌레의 크기로 바꿔주면 됨!

 

매일매일 키워보는 거나 제일 왼쪽 위쪽 다 키우고 적용하는 거나 둘은 같다!

그러니 다 키우고 적용하는게 훨 시간을 줄일 수 있다.

 

* Scanner써서 입력받거나 println으로 출력하면 시간 초과!!!

버퍼나 스트링 빌더를 사용하자!!

전체 코드 

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

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

		int M = Integer.parseInt(st.nextToken()); 
		int N = Integer.parseInt(st.nextToken()); 

		int[][] size = new int[M][M];

		for(int i = 0; i < M; i++) 
			Arrays.fill(size[i], 1);

		for(int n = 0; n < N; n++) {
			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 = M-1; i > 0; i--) { 
				if(zero != 0) {
					zero--;
				} else if(one != 0) {
					one--;
					size[i][0] += 1;
				} else if(two != 0) {
					two--;
					size[i][0] += 2;
				}
			}

			// 제일 위쪽 행 애벌레 키우기 
			for(int i = 0; i < M; i++) {
				if(zero != 0) {
					zero--;
				} else if(one != 0) {
					one--;
					size[0][i] += 1;
				} else if(two != 0) {
					two--;
					size[0][i] += 2;
				}
			}
		}

		// 나머지 애벌레 키우기 
		for(int i = 1; i < M; i++) {
			for(int j = 1; j < M; j++)
				size[i][j] = Math.max(size[i-1][j], Math.max(size[i-1][j-1], size[i][j-1]));
		}
		
		// 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) { 
			for (int j = 0; j < M; j++) 
				sb.append(size[i][j] + " "); 
			sb.append("\n"); 
		}

		System.out.println(sb.toString());
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2310836/src/Main.java

KwonMinha/BOJ