[백준] 17503 파이썬(python) : 맥주 축제

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

17503번: 맥주 축제

 

 

문제의 서론이 너무 길다.  입력값으로 들어오는 선호도와 도수를 정렬해서(도수 기준 오름차순, 같으면 선호도 기준 오름차순) n개의 선호도의 합들이 M을 넘을때 그때의 알코올 도수를 출력하면 된다.

도수 기준 오름차순, 같으면 선호도 기준 오름차순인 이유는 맥주병에 걸리지 않기 위해서 가장 낮은 도수의 맥주부터 정렬하여 다음날 수업에 무리없이 가기 위해서이고 선호도는 n개의 선호도를 모아서 문제에서 주어진 선호도를 넘겨야 하기 떄문이다. 맥주를 n일 동안 계속 마셔야하는데 선호도를 높게 책정해서 기준치를 넘겨버리면 n일을 채우지 않아도 되기 때문이다.

 

import sys, heapq
day, preference, kind = map(int, sys.stdin.readline().split())
bear, heap = [], [] #1
heapq.heapify(heap)
for _ in range(kind):
    each_taste, alch = map(int, sys.stdin.readline().split())
    bear.append((each_taste, alch))
bear.sort(key=lambda x : (x[1], x[0])) #2
find = False
now_alch, prefer_sum = 0, 0
for i in range(kind):
    heapq.heappush(heap, bear[i][0]) #3
    prefer_sum += bear[i][0] #4
    now_alch = bear[i][1] #5
    if len(heap) == day: #6
        if prefer_sum >= preference:
            find = True
            print(now_alch)
            break
        else: #7
            prefer_sum -= heapq.heappop(heap)
if not find: #8
    print(-1)

 

#1 : 선호도와 도수를 저장할 리스트 생성

#2 : 도수가 낮은 순서대로 도수가 같다면 선호도가 낮은 순서대로 정렬

#3 : heap 자료구조에 선호도를 삽입

#4 : 선호도 누적 합

#5 : 현재의 도수

#6 : heap에 맥주가 날짜만큼 쌓였으면 선호도가 기준치를 넘는지 확인하고 넘는다면 그때의 맥주의 도수가 여태까지 중 가장 클테니 도수를 출력하고 break

#7 : 못넘는다면 가장 작은 선호도를 빼주고 누적선호도에서도 빼줌, 그리고 반복

#8 : 기준치 선호도를 못넘는다면 -1 출력

 

정렬에 우선순위 큐를 응용한 문제. 체감 난이도가 높았다. 후에 다시 복기해야지

 

참고한 블로그

https://chinpa.tistory.com/14