백준 30892 - 상어 (파이썬)

https://www.acmicpc.net/problem/30892

풀이

상어가 주어진 크기 T에서 시작하여, K번의 기회를 활용하여 먹이를 먹으며 성장하는 문제이다.

주어진 먹이 리스트 A에서 적절한 먹이를 선택해 T를 최대한 티키우는것이 목표이다.

즉, 그리디 알고리즘을 활용하여 해결할 수 있다. 먹이를 먹는 과정에서 가장 작은 먹이부터 차례로 선택하는 것이 유리하기 때문에 우선순위 큐를 활용한다.

for _ in range(K):
    while pos < N and A[pos] < T:
        pq.put(-A[pos])
        pos += 1

A[pos]가 현재 T보다 작은 경우, 즉 먹을 수 있는 먹이를 pq에 넣는다.

pq.put(-A[pos])를 통해 최대 힙을 구현한다.

• 우선순위 큐는 기본적으로 최소 힙이므로 음수로 변환하여 최대 힙 처럼 사용하는 방식을 선택한다.

시간 복잡도 분석

1. A.sort() → O(N log N)
2. while pos < N → 최대 O(N)
3. pq.put(), pq.get() → O(logN)
4. K번 반복 → O(K Log N)

즉, 총 시간 복잡도는 O(N Log N + K Log N)으로 O(N Log N) 정도이다.

코드

# 백준 30892 - 상어 키우기
# 분류 : 그리디

from queue import PriorityQueue

N, K, T = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
pq = PriorityQueue()

pos = 0
for _ in range(K) :
    while pos < N and A[pos] < T :
        pq.put(-A[pos])
        pos += 1
    
    if pq.qsize() == 0 :
        break

    T += -pq.get()

print(T)