1/2 백준

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

끊어진 기타줄을 구매해야 하는데 6줄 패키지, 낱개를 구매할 수 있다. 지불할 수 있는 방법 중 최소한의 가격을 지불하고 구매할 수 있는 경우를 찾는 문제이다..

내 풀이

broken_string, brand_num = map(int, input().split())
result = 0
package_list, single_list = [], []

for _ in range(brand_num) :
    package, single = map(int, input().split())
    package_list.append(package)
    single_list.append(single)
    
package_min, single_min = min(package_list), min(single_list)
package_num, single_num = broken_string // 6, broken_string % 6

result1 = package_min * package_num + single_min * single_num
result2 = package_min * (package_num + 1)
result3 = single_min * broken_string
result = min(result1, result2, result3)

print(result)

이 문제의 카테고리가 “Greedy” 알고리즘으로 분류가 되어 있어서 나의 풀이보다 다음에 나올 풀이가 더 적절한 풀이인 것 같다.

broken_string, brand = map(int, input().split())
package_list = []
single_list = []

for _ in range(brand) :
    package_price, single_price = map(int, input().split())
    package_list.append(package_price)
    single_list.append(single_price)

min_package = min(package_list)
min_single = 0

result = 0
while broken_string > 0 :
    if broken_string >= 6 :
        min_single = min(single_list) * 6
        broken_string -= 6
    else :
        min_single = min(single_list) * broken_string
        broken_string = 0
        
    if min_single < min_package :
        result += min_single
    else :
        result += min_package
    
print(result)

이렇게 코드를 작성하면 패키지만 사는 경우, 패키지와 낱개 섞어서 사는 경우, 낱개만 사는 경우 모두 커버가 되고 그리디 알고리즘의 취지와 더 잘 맞는 풀이인 것 같다.