[백준] 11946 Fruit Feast / python, 우선순위 큐 정리

문제

Bessie has broken into Farmer John's house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible.

Bessie has a maximum fullness of T (1 ≤ T ≤ 5,000,000). Eating an orange increases her fullness by A, and eating a lemon increases her fullness by B (1 ≤ A, B ≤ T). Additionally, if she wants, Bessie can drink water at most one time, which will instantly decrease her fullness by half (and will round down).

Help Bessie determine the maximum fullness she can achieve!

입력

The first (and only) line has three integers T, A, and B.

출력

A single integer, representing the maximum fullness Bessie can achieve.

 

---

우선순위 큐 문제가 너무 오랜만이라 기억이 잘 안 나서 개념정리도 같이 했다.

힙(Heap) 이란?

• 완전 이진 트리 형태로 되어 있는 자료구조.
• 각 노드의 값이 자식 노드보다 작거나 같다 → 최소 힙
• 각 노드의 값이 자식 노드보다 크거나 같다 → 최대 힙

파이썬에서 힙 자료구조를 사용할 수 있게 해주는 표준 라이브러리가 heapq이다.

heapq는 우선순위 큐를 구현할 때 주로 사용되며, 이진 최소 힙을 기본으로 한다.

heapq는 기본적으로 최소 힙(min-heap)

작은 값이 먼저 나오므로 우선순위가 낮은 수 (작은 수)가 먼저 처리됨

어떻게 최대 힙 ?

우선순위를 반대로 만들고 싶으면 값에 음수(-)를 붙이면 됨.

음수로 넣고, 꺼낼 때 다시 음수 부호를 제거하면 최대 힙처럼 사용 가능

 

✅ heapq.heappop()의 동작 원리

파이썬의 heapq 모듈은 최소 힙(min-heap) 기반
힙의 시간 복잡도 특성 때문에 heappop() 함수는 힙에서 가장 작은 원소 하나만 꺼냄

 

• 삽입 (heappush) : O(log n)
• 꺼내기 (heappop) : O(log n)

여러개를 pop하려면 조건 걸어서 처리

while pq and abs(pq[0][1]) == 3:
    _, val = heapq.heappop(pq)
    print(val)

 

 

+ 튜플의 값 순서대로 정렬 조건

코드

# 우선순위 큐 
import heapq
import sys
input = sys.stdin.readline

def max_fullness(t, a, b):
    visited = [[False] * 2 for _ in range(t+1)] #[fullness][물 마셨는 지]
    pq = [( -0, 0, 0)] # (-fullness, fullness, drank_water)

    max_full = 0

    while pq:
        neg_f, f, water = heapq.heappop(pq)
        visited[f][water] = True
        max_full = max(max_full, f)

        # orange
        if f + a <= t and not visited[f+a][water]:
            heapq.heappush(pq, (-(f + a), f+a, water))
        # lemon
        if f + b <= t and not visited[f+b][water]:
            heapq.heappush(pq, (-(f + b), f+b, water))
        
        if water == 0:
            new_f = f // 2
            if not visited[new_f][1]:
                heapq.heappush(pq, (-new_f, new_f, 1))

    return max_full

t, a, b = map(int, input().split())
print(max_fullness(t, a, b))

 

처음에 기본 최소 힙으로 구현했을 때 시간 초과가 떴다.

하지만 이 문제는 "최대 포만감을 얻는 것"이 목적이기 때문에,
우선순위를 큰 포만감부터 처리해야 탐색 횟수를 줄일 수 있다.

따라서 앞에 포만감의 음수값을 추가해줬고, 정답 처리가 떴다.