[수학/그리디] 백준 1049 기타줄 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1049번: 기타줄

 

 

 

2. 문제 풀이

 M개의 브랜드 제품의 '하나 가격'과 '6개 가격'이 주어질 때, N개를 구입하는 데에 필요한 최소 비용을 구하는 문제입니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

그리디 문제로, 직관적으로 생각하면 쉽게 풀 수 있습니다. M개의 브랜드 중 가장 싼 싱글 가격과 세트 가격을 구한 뒤, 그 둘을 조합해서 제품을 구입합니다.

 보통은 세트 가격이 하나 가격보다 싸므로 N을 6으로 나눈 몫만큼 세트를 구입하고, 나머지를 싱글로 구입하면 됩니다. 하지만, 해당 문제에서 싱글 6개보다 세트 가격이 싸다는 전제가 없습니다. 따라서 모든 경우의 수를 고려해야 합니다.

 

1) 세트만으로 구매하는 경우
2) 몫만큼 세트를, 나머지만큼 싱글을 구매하는 경우
3) 싱글로만 구매하는 경우

 가끔 할인매장에 가면, 동일한 제품 300g짜리가 200g짜리보다 싼 경우가 있죠. 이 문제도, 싱글로 6개를 구매하는 게 세트를 구매하는 것보다 싼 경우가 나올 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
cheap_package = 2000 # 가장 싼 패키지 가격
cheap_single = 2000 # 가장 싼 싱글 가격
for _ in range(M):
    p, s = map(int, input().split())
    cheap_package = min(p, cheap_package)
    cheap_single = min(s, cheap_single)

cost = min(cheap_package*(N//6) + cheap_single*(N%6), cheap_package*(N//6+1), cheap_single*N)
print(cost)

 3가지 조합 중에서 가장 싼 가격을 출력합니다.