[Java] BOJ10836_여왕벌

www.acmicpc.net/problem/10836

10836번: 여왕벌

---

단순 구현 문제이지만 생각보다 시간이 엄청 빡빡했다.

우선 날짜 수가 최대 백만으로 매우 크기 때문에 날짜마다 전체 배열을 업데이트시켜주는 것은 안된다.

 

1. 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다. 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었다고 하자. 모든 입력에서 이렇게 읽은 값들은 감소하지 않는 형태이다.
2. 나머지 애벌레들은 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들이 다 자란 다음, 그 날 가장 많이 자란 애벌레가 자란 만큼 자신도 자란다. 

위의 규칙에서 시간을 줄일 힌트를 발견해야한다. 읽은 값들은 감소하지 않는 형태이기 때문에 나머지 애벌레들의 왼쪽, 왼쪽 위, 위쪽 중에 "위쪽"은 항상 가장 많이 자란 애벌레이다.

따라서 N * 2M-1의 시간복잡도로 제일 왼쪽 열과 제일 위쪽 행의 값을 업데이트한다. 나머지 애벌레들은 자신의 열의 첫 번째 행의 값을 출력하면 된다.

 

*이렇게 하고도 시간초과가 났었는데, 바로 주석 부분인 배열 초기화 과정이다. 단순 이중 포문으로 배열을 초기화할 때는 시간 초과가 났고 Arrays.fill() 함수를 이용할 때는 통과하였다.

둘의 시간복잡도가 얼마나 차이 나는지 정확하게 모르겠으나 Arrays.fill()이 더 빠르다는 것을 알아두면 좋을 것 같다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Bj10836 {

	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[][] arr = new int[M][M];
		for (int i = 0; i < M; i++) {
			Arrays.fill(arr[i], 1);
		}
		/*
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = 1;
			}
		}
		*/
		int N = Integer.parseInt(st.nextToken()); //day
		for (int i = 0; i < N; i++) {
			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 j = M-1; j >= 0; j--) {
				if(zero != 0) {
					zero--;
				} else if(one != 0) {
					arr[j][0] += 1;
					one--;
				} else if(two != 0) {
					arr[j][0] += 2;
					two--;
				}
			}
			for (int j = 1; j <= M-1; j++) {
				if(zero != 0) {
					zero--;
				} else if(one != 0) {
					arr[0][j] += 1;
					one--;
				} else if(two != 0) {
					arr[0][j] += 2;
					two--;
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				if(i != 0 && j != 0) {
					sb.append(arr[0][j]).append(" ");
				} else sb.append(arr[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
}