[백준] 기타줄(1045) - python

✏️ 문제

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.
끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

🎈 입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

🎈 출력

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

🎈 입출력 예

<입력>
4 2
12 3
15 4

<출력>
12

<입력>
10 3
20 8
40 7
60 4

<출력>
36

<입력>
15 1
100 40

<출력>
300
<입력>
9 16
21 25
77 23
23 88
95 43
96 19
59 36
80 13
51 24
15 8
25 61
21 22
3 9
68 68
67 100
83 98
96 57

<출력>
6

👩‍💻 내 코드

이 문제는 그리디 알고리즘을 이용해 푸는 문제이다. 아래와 같은 알고리즘으로 코드를 구현했다.

1. 패키지의 가격과 낱개의 가격을 맞춰 가장 싼 가격을 구한다.
2. 반복해서 최솟값을 구해야하기 때문에 최소힙을 이용한다.

import heapq

N, M = map(int, input().split())

packages, pieces = [], []
for _ in range(M):
    a, b = map(int, input().split())
    packages.append(a)
    pieces.append(b)

result = 0
while N != 0:
    heap = []
    for package in packages:
        heapq.heappush(heap, package)
    if N >= 6:
        for piece in pieces:
            heapq.heappush(heap, piece*6)
        result += (heap[0]*(N//6))
        N %= 6
    else:
        for piece in pieces:
            heapq.heappush(heap, piece*N)
        result += (heap[0])
        N -= N

print(result)