[python] 백준 1049: 기타줄

[python] 백준 1049: 기타줄

1049번: 기타줄 (acmicpc.net)

1049번: 기타줄

실버 4

그리디

---

접근

먼저 기타줄의 브랜드가 여러개가 입력되었다면, 낱개 값의 가장 싼 값과 한팩 값의 가장 싼 값을 입력한 리스트로부터 골라낼 수 있어야 한다. 골라낸 두 값을 가지고 다음의 분기를 결정한다.

 

기타줄 낱개 가격 * 6 < 기타줄 팩이라면 무조건 낱개로만 기타줄을 사는게 싸게 친다.

 

그런데 기타줄 팩 하나를 사는게 더 이득이라면 최대한 기타줄 팩으로 많이 구입하는 것이 가장 싸게 칠 것이다.

문제 조건에서 '적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.' 라 했기 때문에 돈의 수를 최소화 할 수 있다면 필요한 기타줄보다 더 구입하게 되더라도 상관이 없다.

 

구입해야할 기타줄 수가 N개일 때, 기타줄 한팩은 6개로 구성되므로 기타줄 한팩을 최대한 많이 샀을 경우에 남는 기타줄의 개수는 반드시 N%6개가 된다.

 

예를들어 10개의 기타줄을 사야하는 상황에서 기타줄 한팩을 사는 값이 낱개로 6개를 사는 값보다 싼 상황을 가정해보자.

이 조건에서는 기타줄 팩을 최대한 많이 사는 것이 돈을 최소화하는 방법이라 했으므로 기타줄을 2팩을 사는 것이 가장 저렴한 방법이 될 수 있다.

하지만 먼저 한팩을 샀을 경우를 생각해보자. 기타줄 한팩이 6개가 들었으므로 앞으로 더 구매해야할 기타줄은 4개가 된다.

만약 기타줄 낱개의 가격 * 4 < 기타줄 한팩의 값인 상황이 된다면 기타줄 낱개를 4개 사는 것이 돈을 최소화하는 방법이므로 굳이 기타줄 한팩을 더 살 필요가 없어진다.

 

분기점을 정리하면 다음과 같다.

if 기타줄 낱개 가격 *6개 < 기타줄 한팩 가격

기타줄 낱개로 N개를 산다.

 

else :

    if 한팩 단위로 샀을 때 마지막으로 남은 기타줄의 수 * 기타줄 낱개 가격 < 기타줄 한 팩 가격

    기타줄 한팩 가격 * 살 수 있는 최대한의 기타팩의 수(N을 초과하지않는) + 나머지 기타줄 개수 * 기타줄 낱개 가격

    

    else 기타줄 한팩 가격 * 살 수 있는 최대한의 기타팩의 수(N을 초과해도 됨)

 

 

코드

import sys; input = sys.stdin.readline
N, M = map(int, input().split())

pack = [0] * M
one = [0] * M
for i in range(M):
    pack[i], one[i] = map(int, input().split())
min_pack, min_one = min(pack), min(one)

if min_pack > min_one * 6:
    print(N*min_one)
else:
    if (N % 6) * min_one < min_pack:
        print(((N // 6) * min_pack) + ((N % 6) * min_one))
    else:
        print(((N // 6) + 1) * min_pack)