[백준/1049] 기타줄 (Python)

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

1049번: 기타줄

 

Difficulty : Silver 4

 

Status : Solved

 

Time : 00:03:16

 

---

 

문제 설명

 

 

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

 

 

---

 

풀이

 

기본적인 그리디 문제.

우선 M개의 가게에서 패키지 중 가장 싼 패키지와, 낱개 중 가장 싼 낱개만을 고려해주어도 된다. 그렇다면 다음과 같이 생각해 볼 수 있겠다.

• 낱개 x 6이 패키지보다 쌀 경우 : 그냥 낱개로 결제하면 된다.
• 그렇지 않은 경우 :
  • 가능한 한 최대한 패키지로 구매하되, 마지막 나머지 (N % 6, 0에서 5 사이)를 낱개로 사거나, 패키지 하나를 추가로 사는 것 중 더 싼 경우를 택해야 한다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

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

s, t = float('inf'), float('inf')
for _ in range(M) :
  _s, _t = map(int, input().split())
  s = min(s, _s)
  t = min(t, _t)

if s >= t*6 :
  print(t * N)
else :
  print(s * (N // 6) + min(s, t * (N % 6)))

풀이 완료!