[백준 / BOJ] 19582번 : 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여 (JAVA)

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

19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여

아이디어

가장 먼저 떠올린 기본적인 아이디어는 '현재까지 받은 상금 중 가장 큰 값을 지운다' 였다. 시험에 참여할 수 있다면 상금을 획득하고, 상금을 받을 때마다 지금까지 받은 것 중 가장 큰 상금을 업데이트한다. 왜냐하면 상금 한도를 넘어섰을 때, 지금까지 받은 가장 큰 상금을 지워도 넘어갈 수 없다면 이미 2개의 대회를 놓치게 되기 때문이다.

 

따라서 max 변수를 설정해서 매번 받는 상금을 비교하고, 가장 큰 값을 저장해주었다. 그리고 만일 시험에 참여할 수 없게 된다면 지금까지 모은 상금 price에서 max를 빼주고 다시 비교해주었다. 한 번 대회를 뺐다면 flag를 true로 바꾸고, flag가 true인 상태에서 또 대회에 참여하지 못하는 일이 생긴다면(price에서 max를 빼줬는데도 상금 한도보다 큰 경우 포함) Zzz를 출력하도록 했다. 하지만 코드를 제출하자 15%에서 틀렸습니다!가 나왔다.

 

15% 틀렸습니다 : 지나온 대회 vs 현재 대회

내가 놓쳤던 부분은 지나온 대회 중 하나를 포기하는 게 아니라, 현재 대회를 포기하고 그냥 다음 대회로 넘어갈 수도 있단 점이었다. 따라서 현재 대회 상금 한도보다 많은 상금을 갖고 있을 때에는 max 값과 현재 대회에서 받을 상금을 비교하고, 더 큰 값을 포기하도록 했다.

 

하지만 여기에서 멈춘다면 다시 31% 정도에서 틀리게 된다. 질문 게시판에 좋은 반례가 있다.(https://www.acmicpc.net/board/view/55550)

6
1 3
4 5
9 5
7 4
13 2
15 3

 4번째 대회에 임할 때 상금은 13, 한도는 7로 대회에 참여할 수 없다.  지금까지 말한 알고리즘대로라면 가장 큰 상금인 5를 뺄텐데, 그래봤자 상금은 8로 여전히 대회에 참여할 수 없어 "Zzz"를 출력하게 된다.

 

하지만 4번째 대회를 포기하고 넘어간다면? 13 -> 15로 남은 두 대회 모두 출전이 가능하다. 따라서 조건을 하나 더 추가해주었다. 만일 price에서 max를 뺀 값이 여전히 다음 상금 한도보다 크다면, 굳이 이전 대회를 포기하지 말고 이번 대회를 포기하도록 코드를 변경했다.

 

추가

또 작은 문제가 하나 있는데, 만일 마지막 대회까지 아무 대회도 포기하지 않고 지나왔다면 사실 마지막 대회는 참여하든 말든 정답에 큰 상관이 없단 것이다. 1개 대회는 포기해도 상관 없기 때문에 마지막 대회에 다다를 때까지 flag가 false를 유지했다면 그냥 for문을 나가버리도록 했다.

 

전체 코드

// 시간 : 336ms
// 메모리 : 43728KB
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] test = new int[N][2];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());
			
			test[i][0] = x;
			test[i][1] = p;
		}
		
		int max = test[0][1];
		int price = max;
		boolean flag = false;
		boolean ice = false;
		
		for (int i = 1; i < N; i++) {
			if(!flag && i == N - 1) break;
			if(test[i][0] >= price) {
				price += test[i][1];
				max = Math.max(max, test[i][1]);
			} else {
				if(flag) {
					ice = true;
					break;
				}
				flag = true;
				if(test[i][1] < max && price - max <= test[i][0]) {					
					price -= max;
					if(test[i][0] < price) {
						ice = true;
						break;
					} else {
						price += test[i][1];
					}
				}
			}
		}
		System.out.println(ice ? "Zzz" : "Kkeo-eok");
	}

}