[JAVA] 백준 4600번. 정글의법칙 (실버2)

https://www.acmicpc.net/problem/4600

4600번: 정글의 법칙

(문제가 무척 길어서 스크린샷은 생략..)

 

대학교 후배가 실버도장깨기를 하다가 막혔다며 SOS를 친 문제다.

자신만만하게 OK사인을 보내고 문제를 풀러갔다가, 100명도 되지 않는 적은 정답자 수에 놀라고 어마어마하게 긴 문제의 길이에 놀라고 불친절한 Input에 놀라고... 아무튼 생각보다 난이도 있는 문제였다.

 

처음에는 각 나무를 일종의 PriorityQueue처럼 보고 가능한 경우의 수를 모두 계산해서 최적해를 구하는 식으로 짜려고 했는데, 예외와 조건이 너무 많아서 불가능했다.

다른 후배도 같이 도전하던 와중에 그 친구가 먼저 정답을 통과했고, 전체적인 시간을 가지고 관리한다는 tip과 놓치고 있던 조건(최적해를 위해 기다리는것이 금지된다. 건널 수 있으면 바로 건넌다.)을 듣고 바로 구현을 마칠 수 있었다.

 

나무에 대기하고 있는 사람과

다리를 건너고 있는 사람

 

두개의 데이터를 가지고 가장 시간이 적게 걸리는 그룹이 다리를 건너는 시점마다를 트리거로 동작시켜서

빈 다리에 건널 사람이 있다면 채워 넣고, 다리를 건너는 그룹들은 남은 시간을 줄이는 식으로 구현했다.

 

코드는 이렇다.

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

public class Main {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			st = new StringTokenizer(br.readLine());
			int B = Integer.parseInt(st.nextToken())*-1;
			int P = Integer.parseInt(st.nextToken());

			if (B == 0 && P == 0) {
				break;
			}
			int[] trees = new int[B + 1];
			trees[0] = P;
			trees[B] = -P;
			int[][] bridges = new int[B][2];
			int[][] groups = new int[B][2];
			int totalTime = 0;

			for (int b = 0; b < B; b++) {
				st = new StringTokenizer(br.readLine());
				bridges[b][0] = Integer.parseInt(st.nextToken());
				bridges[b][1] = Integer.parseInt(st.nextToken());
			}

			while (trees[B] < 0) {
				int time = Integer.MAX_VALUE;
				for (int b = 0; b < B; b++) {
					if (trees[b] > 0 && groups[b][0] == 0) {
						groups[b][0] = Math.min(trees[b], bridges[b][0]);
						groups[b][1] = bridges[b][1];
						trees[b] -= groups[b][0];
					}
					if (groups[b][1] > 0) {
						time = Math.min(groups[b][1], time);
					}
				}

				totalTime += time;

				for (int b = 0; b < B; b++) {
					if (groups[b][1] > 0) {
						groups[b][1] -= time;
						if (groups[b][1] == 0) {
							trees[b + 1] += groups[b][0];
							groups[b][0] = 0;
						}
					}
				}
			}
			sb.append(totalTime).append("\n");
		}

		System.out.println(sb);
	}
}