BOJ_1781 컵라면

• TOC {:toc}

이 글은 백준 온라인 저지의 1781번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.14

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

N = int(input())
hw = []
for _ in range(N):
    dead, num = map(int, input().split())
    heappush(hw, (-num, dead))

done = []
worked = [False] * (N + 1)
i = 1
while i <= N:
    # i번째 날에 이미 과제를 했으면
    if worked[i]:
        # 다음날로 넘어간다.
        i += 1
        continue
    # 더 남은 과제가 없으면
    if not hw:
        # 반복을 종료한다.
        break

    # 과제를 꺼내서
    num, dead = heappop(hw)
    # 데드라인이 오늘 이전이면
    if dead < i:
        # 넘어간다.
        continue

    while dead > 0:
        # 해당 데드라인에 과제를 하지 않았으면
        if not worked[dead]:
            # 컵라면의 수를 done에 추가하고
            done.append(-num)
            # 과제를 한 상태로 바꾼다.
            worked[dead] = True
            break
        # 과제를 했으면
        # 전날로 이동한다.
        dead -= 1

print(sum(done))

아이디어 & 풀이

최대 힙을 이용해서 컵라면 개수가 큰 숙제부터 꺼내 해결해간다.

오늘의 날짜 i가 N보다 작거나 같을 동안 아래의 과정을 반복한다. * 더 남은 과제가 없으면 반복을 종료한다.

우선 해당 날짜에 이미 숙제를 했으면 다음 날로 넘어간다.

• N일 까지의 각 하루(인덱스)에 대해서 그날에 숙제를 했는지 아닌지를 표시하는 worked 리스트를 만들어 관리한다.

다음으로 컵라면의 수가 최대인 과제를 꺼내서

• 데드라인이 오늘 이전이면 다음 과제로 넘어간다.
• 해당 데드라인에 과제를 하지 않았으면 해당 과제의 컵라면 수를 done에 추가하고 worked[dead]를 True로 바꿔 과제를 한 상태로 바꾼다.
• 해당 데드라인에 과제를 이미 했으면
  • 이전에 이미 한 과제가 현재 과제보다 더 많은 컵라면을 제공하고
  • 해당 과제는 데드라인 이전에는 할 수 있기 때문에
  • 데드라인을 하나 줄여나가면서 아직 과제를 하지 않은 날을 찾아 위의 과정을 반복한다.

디버그

• 시간초과가 계속 났다.
  • 처음에는 ‘데드라인’을 기준으로 순회하면서 해당 데드라인의 컵라면 수 중 현재 done 안의 컵라면 수보다 큰 게 있으면 bisect를 이용해서 현재 done의 컵라면 수를 교체하는 방식으로 작성했다.
    • 모든 과제를 다 순회하면서 bisect를 너무 많이 사용했기 때문인 것 같다.
  • 두 번째는 위의 아이디어 & 풀이와 같은 방법인데, 해당 데드라인에 이미 과제를 한 상태일 때 heappush를 이용해서 데드라인을 하나 줄인 원소를 다시 집어넣었다.
    • 위처럼 바로 이전의 날짜들에 대해서 아직 일하지 않은 날을 찾으면 되는데, 이 과정을 불필요한 heappush와 heappop으로 대신해서 시간이 오래 걸린 것 같다.

피드백

• 이번에도 틀린 풀이의 ‘아이디어 & 풀이’ 부분을 정리하면서 코드를 수정해 제출하는 과정에서 정답 처리가 되었다. 이걸 다른 답을 찾아보고 제출하기 전에 하면 참 좋을 텐데, 오랜 시간 못 푼 상태로 있다 보면 그럴 생각이 잘 들지 않는 것 같다. 다음에는 꼭 상기시켜서 조금 쉰 다음에 다시 시도해봐야겠다.

참고 답안

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

hw = [tuple(map(int, input().split())) for _ in range(int(input()))]
hw.sort()

done = []
for dead, num in hw:
    heappush(done, num)
    if len(done) > dead:
        heappop(done)

print(sum(done))

아이디어 & 풀이

과제를 데드라인에 대해 정렬한 뒤 모든 과제를 순환하면서 과제를 done에 집어넣는다.

• 해당 데드라인 까지는 데드라인 개수의 과제만 할 수 있다.
• 그러므로 과제를 넣은 뒤 한 과제의 수(i.e., done의 원소 개수)가 데드라인보다 크면 done에서 과제를 제거한다.
  • heappop을 이용하면 컵라면 수가 최소인 과제를 제거할 수 있다.
  • 이는 컵라면 수가 최소인 과제 대신 지금 넣은 과제를 하는 것으로 생각할 수 있다.
  • 지금 넣은 과제의 데드라인은 이전에 넣은 과제보다 크거나 같아서 컵라면 수가 최소인 과제를 하는 날에 지금 넣은 과제를 하는 것은 문제가 되지 않는다.