[백준] 1781 컵라면

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

1781번: 컵라면

문제 당 마감시간과 보상이 주어지고, 이때 보상이 최대 수를 구하는 문제

 

 

접근

 

주어진 마감 시간 내에 최대 보상을 얻어야 하므로, 탐욕적 알고리즘 사용

배열을 이용하여 문제를 풀려고 해보았으나, 계속 결과가 시간 초과로 나와서 우선순위 큐 사용 

참고로, 우선순위 큐를 사용하면 검색 속도가 배열의 경우보다 훨씬 빠르다.

 

 

 

풀이

 

우선 마감시간을 기준으로 문제를 정렬한다.

이후 같은 마감시간 내에서 보상이 가장 큰 문제를 선택하면 될 것 같지만, "[1, 1], [2, 1], [3, 4], [3, 7]" 과 같이 마감시간이 남았음에도 보상이 더 큰 경우를 고려해주어야 한다.  

 

이를 구현하기 위해 count 메소드를 이용하여, 이미 선택된 것 중에서 마감시간이 중복된 것이 있다면 마감시간이 더 짧다는 가정하에 다시 중복을 체크하는 방식을 사용해보았다.

 

...
j_n = int(out.count(x[0])) # 마감시간 중복체크
j = 0

while j <= j_n : 
	overlapping = int(out.count(x[0] - j))
    
    if overlapping == 0 : # 중복되지 않는다면
    	out.appen(x[0] - j) 
        sum += x[1]
        break
    else : j += 1

마감시간이 더 짧다고 가정하는 이유는, 마감 시간의 중복체크에서 다름에 걸리지 않기 위함이다. 이렇게 하므로서 out 함수에는 실질적으로 해당 문제를 끝낸 시간이 나타나게 된다.

 

하지만 이 방법의 경우, 큐에 모든 문제를 삽입한 후 중복을 다 고려해야 하기때문에 여전히 제한 시간을 초과하게 된다.

 

 

제한을 초과하지 않기 위해서는, 삽입 시 마감시간을 넘어서는 문제를 제거해야만 한다.

for i in num : 
    deadline = i[0]
    que.put(i[1]) 
    while que.qsize() > deadline : # 데드라인이 더 길다면 제거 
        que.get()

위와 같이 큐의 사이즈와 마감 시간을 비교하면 마감시간을 초과하는지 확인할 수 있다.

 

 

 

코드

import sys
from queue import PriorityQueue
# 시간 단축을 위해 우선순위 큐를 사용한다.

n = int(sys.stdin.readline()) # input 보다 속도가 빨라~!
num = [] # 컵라면을 받음

for i in range(0, n) : 
    num.append(list(map(int, sys.stdin.readline().split())))
    # n개의 문제를 받음

num.sort(key = lambda num : (num[0], -num[1])) # 마감시간이 빠르고, 보상이 큰 순으로.
que = PriorityQueue()

for i in num : 
    deadline = i[0]
    que.put(i[1]) 
    while que.qsize() > deadline : # 현재 데드라인이 더 길면 제거 
        que.get()

sum_ = 0
while not que.empty() : 
    sum_ += que.get()
        
print(sum_)

 

 

 

후기

 

늘 그렇지만.. 혼자 이상한 방향에 빠지면 잘 나오지 못하는 것 같다.

문제를 다양한 시간으로 바라보면서도 고려사항을 꼼꼼히 체크하는 게 참 중요하다고 느낀다.