[백준] 1781 - 컵라면

1. 문제

1781번: 컵라면

2. 개요

N개의 문제와 각 문제의 데드라인, 각 문제를 풀었을 경우 받을 수 있는 컵라면의 개수가 주어진다.

문제에 걸리는 시간이 1이라고 할 때, 얻을 수 있는 컵라면의 최대 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

처음에는 얻을 수 있는 컵라면의 갯수가 최대인 문제를 먼저 빈 공간에 끼워나가는 식으로 풀어봤다.

답은 잘 나오는것 같았지만, 시간초과를 해결하지 못했다.

3-2. Python (시간초과)

import sys
import heapq

N = int(sys.stdin.readline())

problems = []
answer = 0
sched = [0 for i in range(N+1)]
for i in range(N):
    d, r = map(int, sys.stdin.readline().split())
    heapq.heappush(problems, [r * -1, d])

while problems:
    now = heapq.heappop(problems)
    for i in range(now[1], 0, -1):
        if sched[i] < now[0] * -1:
            answer += now[0] * -1 - sched[i]
            sched[i] = now[0] * -1
            break

print(answer)

애초에 데드라인이 짧은 문제부터 탐색하며 컵라면의 갯수를 우선순위 큐에 넣어간다.

우선순위 큐의 길이가 현재 탐색하는 문제의 데드라인보다 길다면, 얻을 수 있는 컵라면의 개수가 가장 작은 것을 빼내는 작업을 반복하여 정답을 구한다.

3-3. Python

import sys
import heapq

N = int(sys.stdin.readline())

problems = []
answer = 0

maxdate = 0
for i in range(N):
    problems.append(list(map(int, sys.stdin.readline().split())))

problems.sort()

todo = []

for p in problems:
    heapq.heappush(todo, p[1])
    answer += p[1]

    if len(todo) > p[0]:
        answer -= heapq.heappop(todo)

print(answer)

3-4. C#

static void Main(string[] args)
{
    int N = int.Parse(Console.ReadLine());

    int answer = 0;
    List<int[]> problems = new List<int[]>();
    
    
    for (int i = 0; i < N; i++)
    {
        problems.Add(new int[] { 0, 0 });
        string[] problem = Console.ReadLine().Split();
        problems[i][0] = int.Parse(problem[0]);
        problems[i][1] = int.Parse(problem[1]);
    }

    problems = problems.OrderBy(a => a[0]).ToList();

    PriorityQueue<int, int> todo = new PriorityQueue<int, int>();

    foreach (int[] p in problems)
    {
        todo.Enqueue(p[1], p[1]);
        answer += p[1];

        if (todo.Count > p[0])
            answer -= todo.Dequeue();
    }

    Console.WriteLine(answer);
}