(Python) - BOJ(1049번) : 기타줄

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

1049번: 기타줄

 

• 해설 :

기타리스트 강토가 기타줄을 갈려고 한다. 갈아야 할 기타줄의 수 N과 가격을 찾아본 브랜드 M이 주어지고, 브랜드 별 패키지(기타줄 6개 묶음) 의 가격과 낱개의 가격이 주어진다. 이 때, 기타줄을 가는데 드는 최소 비용을 찾는 문제이다.

 

 

 

 

• 풀이 :

그리디 알고리즘을 사용하는 쉬운 문제이다.

낱개의 가격이 가장 싼 브랜드와, 묶음의 가격이 가장 싼 브랜드를 찾고 

낱개 * (사야하는 기타줄의 수) 와 묶음 * (사야하는 기타줄의 수 / 6) 의 값을 비교하여 더 싼 방법을 찾은 후 정답에 더해주면 된다. 이 때, 6개 단위로 끊어서 사야 낱개와 패키지의 가격을 올바르게 비교할 수 있다.

 

 

 

 

value, brand = map(int,input().split())
pay_set = []
pay_single = []
for i in range(brand):
    x,y=map(int,input().split())
    pay_set.append(x)
    pay_single.append(y)
pay_set.sort()
pay_single.sort()
pay = 0
if pay_set[0] < pay_single[0]*6:
    while value >= 6:
        value -= 6
        pay+=pay_set[0]
    while value > 0:
        if value*pay_single[0]<pay_set[0]:
            value -= 1
            pay += pay_single[0]
        else:
            value=0
            pay+=pay_set[0]
else:
    pay = pay_single[0]*value
print(pay)