[백준17503/실버1] 맥주 축제 - Python

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

 

어떻게 풀어야할지 꽤 오래 고민했다.

먼저 힙 없이 정렬하고 풀었는데 시간초과나서 힙으로 다시 구했다.

 

1. 도수레벨 기준으로 정렬 (도수 낮은 것 부터 순회하기 위해)

2. 맥주 리스트 순회하면서 하나씩 선택하기

2-1. 선택할 때 N개 아직 다 안찼으면 heappush

3. push 하고나서 N개 꽉 찼으면 선호도 M 채웠는지 확인

3-1. 선호도 M 채웠으면 최소 도수 레벨 갱신 (도수 레벨도 작은 것부터 순회하므로 현재 값으로 갱신)

3-2. 선호도 M 못채웠으면 가장 작은 선호도를 가진 맥주 뺴기 heappop

4. N개 맥주 다 못채웠으면 계속 for문 순회하며 반복

 

# 성공 코드 1

# 89144 KB, 732 ms

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

N, M, K = map(int, input().split())  # 기간, 선호도의 합, 맥주 종류
beers = [list(map(int, input().split())) for _ in range(K)] # 선호도, 도수레벨
beers.sort(key=lambda x: x[1])

total = 0
heap = []
result = 0

for v, c in beers:
    if len(heap) < N:
        heappush(heap, (v, c))
        total += v

        if len(heap) == N:
            if total >= M:
                result = c
            else:
                total -= heappop(heap)[0]

print(result if result != 0 else -1)

 

 

풀고보니 이분탐색 문제라 그것도 풀어봤다.

 

1. 선호도 높은 것부터 조건 확인하기 위해 reverse=True로 정렬

2. low, max 값은 맥주 리스트의 도수레벨중 최소와 최대

3. low <= high 조건 동안 while문 돌며 이분탐색

3-1. 도수 레벨을 정한 후, 맥주 리스트를 선호도가 높은 것부터 순회하며 총 선호도와 맥주 수 카운팅

3-2. N개 꽉 찼으면 break (선호도가 큰것부터 순회했으므로 지금이 최댓값)

3-3. 조건에 맞으면 (선호도 M이상, 맥주 N개) result 갱신 후, 더 작은 도수레벨 탐색 (high = mid - 1)

3-4. 조건에 안맞으면 더 높은 도수레벨 탐색 (low = mid + 1)

 

이렇게 풀었더니 시간은 거의 6배정도 차이났다.

 

# 성공 코드 2

# python 73692 KB, 4292 ms

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())  # 기간, 선호도의 합, 맥주 종류
beers = [list(map(int, input().split())) for _ in range(K)] # 선호도, 도수레벨
beers.sort(reverse=True)

low = min(c for v, c in beers)
high = max(c for v, c in beers)
result = float('inf')

while low <= high:
    mid = (low + high) // 2
    total = 0
    cnt = 0

    for v, c in beers:
        if c <= mid:
            total += v
            cnt += 1
        if cnt == N:
            break

    if total >= M and cnt == N:
        result = mid
        high = mid - 1

    else:
        low = mid + 1

print(result if result != float('inf') else -1)

 

 

이런 문제를 보면 그리디로 풀어야할지, 이분탐색으로 풀어야할지, dp로 풀어야할지 아직 헷갈린다. 더 많이 풀어봐야겠다~