백준 1781) 컵라면 C++

1781번: 컵라면 (acmicpc.net)

1781번: 컵라면

문제

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호데드라인컵라면 수

1	2	3	4	5	6	7
1	1	3	3	2	2	6
6	7	2	1	4	5	1

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 2^31보다 작거나 같은 자연수이다.

입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

예제 입력 1 복사

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

예제 출력 1 복사

15

 

메인 알고리즘 - 그리드알고리즘

 

문제 조건이 컵라면을 최대한 많이 가져가야된다고 한다.

이 말은 컵라면이 높은 문제부터 나열했을 때 그 문제를 풀 수 있으면, 푸는 편이 매우 유리하다.

 

그러나 단순히 컵라면을 오름차순으로 해서는 이 문제에 접근하기 어렵다.

증명할 순 없지만, 잘 분포된 오름차순으로 정렬된 데이터 케이스들에 관해선

처음 1~n개의 문제들은 최적의 해에 반드시 들어갈 문제들이긴 하나,

 

문제를 담으면 담을수록, 여태까지 담은 문제들을 비교해서 이 문제가 데드라인에 만족하는지 

확인 하는데  어려움을 겪을 수 있다. 

 

파라메트릭 서치를 이용해서 log n의 속도로 확인해서 삽입하면 되지 않나요?

 

데드라인이 큰 문제가 들어오고나서 그보다 데드라인이 작은 문제가 들어왔을 경우

데드라인의 조건이 한칸씩 밀리기 때문에 모든 배열을 확인해야 됨으로

만약 데드라인과 컵라면의 수가 오름차순인 데이터 케이스가 들어올 경우 완전탐색을 통해 해결해야 될 것이다.

 

그럼 데드라인을 내림차순 컵라면을 오름차순으로 정렬한다면 해결되는 것이 아닌가?

 

거의 근접했으나, 데드라인을 내림차순으로 정렬하는 과정에서 컵라면이 완벽한 오름차순이 되지 않기 때문에

단순히 데드라인에 만족하는 값을 그리드 알고리즘으로 골라담았다간

 

1 10

2 11

2 12

이라는 데이터 케이스에 1 10을 먼저 담아 23이라는 답을 내지 못할 것이다.

 

이 문제를 해결하는 방법은 발상하기 조금 어려운데

최장 증가 수열의 길이를 구하는 알고리즘과 비슷한 방식이다.

 

먼저 한번 언급된 것 처럼 

데드라인을 기준으로 내림차순 컵라면을 기준으로 올림차순으로 정렬한다.

그다음 우리가 선택할 문제들을 담은 내림차순 우선순위 큐를 하나 추가해서

 

순회를 하면서 데드라인에 만족하는 값을 발견할 때마다 정답을 담을 우선순위 큐에 넣을 것이다.

데드라인이 내림차순으로 진행되기 때문에 우선순위 큐의 크기보다 크다면 push를 하도록 한다면

큐에 담긴 문제들은 최적의 해는 아닐지라도 데드라인을 위반하는 해는 아니게 된다.

 

우리는 최대한 많은 문제를 풀어야함으로 조건을 만족하는 이상 큐에 넣는 건 합당하다.

그러나 이 문제가 과연 최적의 해에 포함되었는가를 확인해야 되는데

 

순회를 하면서 데드라인을 위반한 데이터를 발견했을 때 우선순위 큐를 통해 top() (가장 낮은 값) 과 비교한다.

만약 데드라인을 위반한 데이터가 내가 담은 가장 낮은 값보다 크다면  pop()하여 낮은 값을 빼고

해당 문제의 컵라면 수를 push한다. 그럼 내가 푼 문제수는 변하지 않으며 컵라면의 갯수만 늘어난다.

만약 top보다 작다면 그 문제는 그대로 넘어간다.

 

이 과정을 반복하면

항상 우선순위 큐로는 데드라인을 만족하는 문제만 들어오게 되어 있으며

우선순위 큐의 가장 낮은 값을 pop과 push를 통해 컵라면이 많은 문제로 교체되기 때문에 최적의 해를 구할 수 있다. 

 

 

Small talk about Game

 

스케줄링 문제의 일종인데 일정조건(데드라인)안에 가장 높은 효율(컵라면)을 골라준다는 점에서

타이쿤류의 자동 주문이라던가 rpg게임의 자동 선택등에 쓰이기 매우 적합해 보인다고 생각이 든다.