[백준 / BOJ] 30205번 : 전역 임무 - JAVA

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

30205번: 전역 임무

우선순위 큐 PriorityQueue

김 병장이 전역을 하기 위해서는 항상 전투력 P를 최대로 유지할 필요가 있다. 다행히 적군과 싸워도 P가 깎이지는 않으므로, 최대한 큰 값을 만들도록 +연산과 *연산을 조절해야 한다.

 

어떻게 해야 P가 최댓값을 계속 가질 수 있을까? 마이너스 연산이 없기 때문에, 할 수 있는 한 최대로 + 연산을 하고, 그 결괏값에 *2 연산을 해주면 최댓값을 얻을 수 있다.

 

1. 각 층에서 -1을 제외한 값을 정렬하고, 작은 순서대로 김 병장과 싸우게 한다. 김 병장의 P보다 공격력이 작거나 같다면 P에 적군의 공격력을 더해준다.
2. 만일 김 병장의 P보다 큰 적군이 나타난다면 -1이 남아 있는지 확인한다. 그리고 P가 적군보다 커지거나, 혹은 -1 개수가 0이 될 때까지 P를 두 배로 늘려준다.
3. 적군을 모두 해치운 후, 남은 -1의 개수만큼 P를 두 배씩 늘려준다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 시간 : 476ms
// 메모리 : 51172KB
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 N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		long P = Long.parseLong(st.nextToken());
		
		PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});
		
		int twice = 0;
		for (int i = 0; i < N; i++) {
			twice = 0;
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int n = Integer.parseInt(st.nextToken());
				if(n == -1) twice++;
				else que.offer(n);
			}
			
			while(!que.isEmpty()) {
				int cur = que.poll();
				if(cur <= P) {
					P += cur;
				} else {
					while(twice > 0 && P < cur) {
						twice--;
						P *= 2;
					}
					if(P < cur) {
						System.out.println(0);
						return;
					} else {
						P += cur;
					}
				}
			}
			
			while(twice > 0) {
				P *= 2;
				twice--;
			}
		}
		System.out.println(1);
		
	}

}