(JAVA) 백준 1781번 : 컵라면 -- [그리디]

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

1781번: 컵라면

 

안녕하세요.

그리디 알고리즘과 우선순위 큐를 활용해 해결했습니다.

 

처음에 데드라인 이란 단어의 정의가 헷갈려 풀이 방향을 잘못잡았었습니다.

 

풀고자 하는 문제를 포함하여 이전까지 풀었던 개수가 해당 문제의 데드라인보다 같거나 작아야합니다.

 

 

즉,

1) 데드라인이 작을 수록

2) 데드라인이 같을 때 획득할 수 있는 컵라면의 개수가 클 수록

 

해당하는 문제들을 푸는 것이 가장 많은 컵라면을 획득할 수 있습니다.

 

 

 

이를 위해 문제와 데드라인을 변수로 갖는 문제 클래스를 하나 선언하고, 입력 받은 값을 활용해 클래스 객체를 만들어냅니다.

하나의 Array안에 하나 씩 집어넣고, 위 조건에 맞게 sort하기 위해 문제 클래스에서 Comparable 인터페이스를 구현합니다.

 

다음, 문제를 풀어 획득한 컵라면의 개수를 담는 우선순위 큐를 생성합니다.

  -> 이 우선순위큐는 default 설정값으로 오름차순대로 poll하기 때문에, 가장 우선시되게 꺼내는 값은 획득하는 컵라면의 개수가 작은 문제입니다.

 

여기서부터 중요한데요.

 

이렇게 우선순위큐를 만들고 Array를 정렬한 이유는

 

 

데드라인이 작은 문제들부터 풀어야 많이 풀 수 있다.  는 것과

데드라인의 크기에 상관없이 더 많은 컵라면을 획득하는 것이 중요하다 는 것입니다.

 

 

그래서,

 

input)

2 100

2 100

3 500

3 500

 

이 주어지면

2 100, 2 100, 3 500을 선택하는 것 보다

2 100, 3 500, 3 500을 선택하는 것이 더 많은 컵라면을 얻을 수 있습니다.

 

 

다시 본론으로 돌아와서,

 

우선순위 큐의 원소 개수 : 전체 푼 문제 개수

우선순위 큐의 원소 : 푼 문제를 통해 얻은 컵라면 개수

 

라고 했을 때

 

우선순위 큐의 원소 개수가 데드라인보다 작으면

  -> 바로 해당 문제 넣기

우선순위 큐의 원소 개수가 데드라인보다 같거나 크면

  -> peek해서 가장 top에 있는 원소의 컵라면 수 확인

  -> 현재 문제의 컵라면 획득 개수가 더 많다 싶으면 poll해서 풀었던 문제 버리고 현재 문제 넣기

 

이를 Array for문탐색 O(n)으로 끝낸다.

 

그 후 우선순위 큐에 있는 원소 컵라면 수를 전부 더하면 끝!

 

 

 

이상입니다.

 

감사합니다!

 

소스코드

---