[백준][1049] 기타줄

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

문제

• N개의 기타줄을 교체하려고 할 때 필요한 돈의 최솟값을 구한다.
• 이 때 기타줄 M개의 브랜드에서 패키지(6개)와 낱개로 기타줄을 팔고 있다.
• 패키지와 낱개를 섞어서 M개의 기타줄을 최소 금액으로 구매해보자.

입력

• 첫째 줄, N과 M이 주어진다.
• 다음 줄, M개의 줄에는 각 브랜즈의 패키지 가격과 낱개의 가격이 구분하여 주어진다.

출력

• 첫째 줄, 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값

풀이

우선 패키지 중에 제일 값이 싼 패키지와 낱개 중 가장 값이 싼 낱개의 가격을 입력을 받는 동시에 구한다.

n, m = map(int, input().split())
min_package = 1000
min_each = 1000
for _ in range(m):
    package, each = map(int, input().split())
    min_package = min(package, min_package)
    min_each = min(each, min_each)

기타줄을 살 때 2가지의 경우가 있을 수 있다.

1. 필요한 기타 줄이 6개보다 많은 경우
   패키지 가격과 6 * 낱개 가격 중 더 작은 값을 골라 6개씩 구매한다. 따라서 패키지 또는 낱개를 6개씩 구매할 수 있는 만큼 구매한다.따라서 다음과 같은 공식으로 쓸 수 있다.

   $price = price + (n//6) * min(package, each * 6)$

2. 필요한 기타 줄이 6개보다 적은 경우
   패키지 가격과 남은 개수 * 날개 가격 중 더 작은 값을 골라 구매한다. 따라서 다음과 같은 공식으로 쓸 수 있다.

   $price = price + min(package, each * remain\,count)$

따라서 위 1번, 2번 케이스를 거쳐 최소 값을 구할 수 있다. n이 6보다 작을때에도 1번 경우에 포함시켜도 되는 이유는 n이 6보다 작으면 나눈 몫이 0이 나와서 값이 그대로 유지되기 때문이다. 따라서 결국 모든 케이스에 대해 다음과 같은 공식을 적용시킬 수 있다.

실제로 다음과 같이 코드로 구현했다.

ans = (n // 6) * min(min_package, min_each * 6) + min(min_package, min_each * (n % 6))

코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
min_package = 1000
min_each = 1000
for _ in range(m):
    package, each = map(int, input().split())
    min_package = min(package, min_package)
    min_each = min(each, min_each)

ans = (n // 6) * min(min_package, min_each * 6) + min(min_package, min_each * (n % 6))

print(ans)