BOJ - 1781 컵라면

leehyunjon·2022년 6월 13일

boj 그리디 우선순위 큐

Algorithm

목록 보기

66/162

1781 컵라면 : https://www.acmicpc.net/problem/1781

Problem

Solve

처음 문제를 보고 이게 골드2 문제라고 생각을 하고 풀었지만 역시 반례는 존재했다.

처음 풀이는 그저 데드라인 기준 오름차순 정렬, 컵라면 수 내림차순 정렬 한 후 각 데드라인의 첫번째 컵라면 수를 더하면 되는 줄 알았다.

하지만 문제를 잘 보면 데드라인이라는 용어에 반례가 숨겨져있었다.

데드라인이란 그 시간까지 해결해야하는 것이기 때문에 이전에 해결해도 인정되는 것이다.
그 말은 데드라인이 3인 문제를 데드라인이 1인 날에 풀어도 되는 것이고 6인 문제를 1에 풀어도 된다는 것이다.

데드라인이 가장 늦은 날 부터 빠른 날 순으로 PQ에 해당 날에 풀수 있는 문제의 컵라면 수를 넣어준다. 이 때 PQ는 컵라면 수 내림차순으로 정렬한다.
그렇게 되면 해당 날에 풀수 있는 문제 중 컵라면 수가 가장 많은 문제를 해결해가면 최대의 컵라면 수를 얻게 되는것이다.

예를 들어
5 5
4 6
4 12
3 8
4 18
2 10
2 5
1 7
1 14 가 주어진다면

1일날 14개
2일날 10개
3일날 18개
4일날 12개
5일날 5개
로 총 59개의 컵라면이 최대로 받을 수 있는 개수이다.
3일 날 데드라인이 3인 문제는 8개지만 데드라인이 4이고 18개를 받을수 있는 문제를 푸는게 더 많이 받을수 있다

Code

public class 컵라면 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		Problem[] problems = new Problem[N];
		int lastDeadLine = 0;
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int deadLine = Integer.parseInt(st.nextToken());
			int noodle = Integer.parseInt(st.nextToken());
			problems[i] = new Problem(i, deadLine, noodle);

			lastDeadLine = Math.max(lastDeadLine, deadLine);
		}

		//각 데드라인 별 받을 수 있는 컵라면 개수 리스트
		List<Integer>[] noodles = new List[lastDeadLine + 1];
		for (int i = 1; i < noodles.length; i++) {
			noodles[i] = new ArrayList<>();
		}

		for (Problem problem : problems) {
			noodles[problem.deadLine].add(problem.noodle);
		}

		//컵라면 개수 내림차순
		PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		});

		int answer = 0;

		//가장 데드라인이 느린 날 부터
		for (int i = noodles.length - 1; i >= 1; i--) {
        	//해당 날짜에 풀수 있는 문제의 컵라면 수 누적
			for(int noodle : noodles[i]){
            	//문제 중 가장 많은 컵라면 수
				pq.offer(noodle);
			}

			if(pq.isEmpty()) continue;

			//컵라면 개수 갱신
			answer += pq.poll();
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static class Problem {
		int num;
		int deadLine;
		int noodle;

		public Problem(int num, int deadLine, int noodle) {
			this.num = num;
			this.deadLine = deadLine;
			this.noodle = noodle;
		}
	}
}