[BOJ 1781] 컵라면 (Python)
[BOJ 1781] 컵라면
풀이
같은 데드라인 문제들 중에서 받을 수 있는 컵라면 개수가 최대인 1문제를 선택해서 푸는 것으로 접근했다. 데드라인 마다 모든 문제들을 탐색하면 O(N²)
으로 시간초과를 예상했다. 따라서 우선순위 큐를 이용하자는 생각을 하였고, 맞는 방법이었다.
# 잘못된 코드
import sys
import heapq
input = sys.stdin.readline
N = int(input())
problem = []
for _ in range(N):
heapq.heappush(problem, list(map(int, input().split())))
explore = []
ramen = 0
for i in range(1, N):
while problem and problem[0][0] == i:
heapq.heappush(explore, -heapq.heappop(problem)[1])
if explore:
ramen -= heapq.heappop(explore)
while explore:
heapq.heappop(explore)
print(ramen)
이렇게 구현했지만 틀렸다. 올바른 로직이 아닌 것을 알 수 있었다. 위처럼 구현하게 되면 문제에 있는 입력 예제는 맞을 수 있으나 다른 예제에서 틀리게된다.(각각 데드라인 하나에 문제 딱 하나만 점검하기 때문에 틀림.) 아래 예제를 통해 설명하겠다.
(Ex)
데드라인 : 3 / 3 / 3 / 4 / 4
컵라면수 : 2 / 5 / 9 / 2 / 4
데드라인이 1과 2인 문제들이 없는 것을 알 수 있다. 이 경우에는 데드라인이 3인 문제를 모두 푸는 것이 컵라면을 최대로 받을 수 있으며, 마지막으로 (4,4) 문제를 풀면 컵라면을 최대로 받을 수 있게된다. 이러한 경우를 꼭 생각해주는 연습을 많이 해야겠다...
-
[(데드라인, 컵라면수)]
를 오름차순 정렬한다. -
맨 앞의 문제부터 일단 푼다. (우선순위 큐에 풀 문제를 저장한다.)
-
현재 푼 문제의 데드라인이 / 현재 + 이전에 풀었던 문제들 수보다 작으면 우선순위 큐에서 제일 작은 값을 삭제한다. (Min Heap)
코드
import sys
import heapq
input = sys.stdin.readline
N = int(input())
problems = [list(map(int, input().split())) for _ in range(N)]
problems.sort()
explore = []
for problem in problems:
# 일단 문제 풀어본다.
heapq.heappush(explore, problem[1])
# 데드라인이 같은 문제를 풀었을 때 컵라면 최대로 받을 수 있는 문제만 풀도록 함.
if problem[0] < len(explore):
heapq.heappop(explore) # Min Heap 으로 오름차순 / 제일 작은 컵라면 문제 제거
print(sum(explore))
Author And Source
이 문제에 관하여([BOJ 1781] 컵라면 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kimdukbae/BOJ-1781-컵라면-Python
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
import heapq
input = sys.stdin.readline
N = int(input())
problems = [list(map(int, input().split())) for _ in range(N)]
problems.sort()
explore = []
for problem in problems:
# 일단 문제 풀어본다.
heapq.heappush(explore, problem[1])
# 데드라인이 같은 문제를 풀었을 때 컵라면 최대로 받을 수 있는 문제만 풀도록 함.
if problem[0] < len(explore):
heapq.heappop(explore) # Min Heap 으로 오름차순 / 제일 작은 컵라면 문제 제거
print(sum(explore))
Author And Source
이 문제에 관하여([BOJ 1781] 컵라면 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimdukbae/BOJ-1781-컵라면-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)