백준 1049번 파이썬 풀이: 기타줄

백준 1049번 기타줄

 

알고리즘 분류: 수학

 

링크: www.acmicpc.net/problem/1049

 

1049번: 기타줄

문제

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

 

 

문제 파악

 

이 문제의 핵심은 되도록 돈을 적게 쓰는 것이다.

 

6개 패키지 기타줄을 사서 기타줄이 남더라도 낱개로 사는것보다 싸다면 6개짜리를 택하는게 핵심이다.

 

예를 들어 예제 3번처럼 끊어진 기타줄이 15개고 브랜드는 1개일 때

 

6개 패키지는 100원이고 낱개는 40원이다.

 

6개 패키지를 2개사고 낱개로 3개를 사면 320원인데

6개 패키지를 3개사면 기타줄이 3개 남더라도 300원으로 더 싸다.

 

현명한 소비자인 강토는 이런식으로 가장 돈이 적게들게 소비를 하는 것이다.

 

 

코드

# 1049번

n, m = map(int, input().split())

answer = 0
price_list = []

for _ in range(m):
    price = tuple(map(int, input().split()))
    price_list.append(price)

six_list = sorted(price_list, key=lambda x : x[0])
one_list = sorted(price_list, key=lambda x : x[1])

if six_list[0][0] <= one_list[0][1] * 6:
    answer = six_list[0][0] * (n // 6) + one_list[0][1] * (n % 6)
    if six_list[0][0] < one_list[0][1] * (n % 6):
        answer = six_list[0][0] * (n//6 + 1)
else:
    answer = one_list[0][1] * n

print(answer)

브랜드 개수가 m개로 주어지지만 우리는 가격을 최소로 하는게 목적이기 때문에

 

다른 가격보다 제일 가격이 낮은 브랜드만 찾으면된다.

 

6개 패키지 가격이 제일 싼 순서로 정렬한 리스트를 six_list로 하고

 

낱개 가격이 제일 싼 순서로 정렬한 리스트를 one_list로 한다.

 

six_list의 [0][0] 인덱스는 6개 패키지 가격이 가장 싼 물건이고

 

one_list의 [0][1] 인덱스는 낱개 가격이 가장 싼 물건일 것이다.

 

six_list의 [0][0] 인덱스가 one_list의 [0][1] 인덱스를 6개 사는것보다 싸거나 같다면

 

n을 6으로 나눠서 몫만큼 six_list에서 사고 나머지만큼 one_list에서 사면 된다.

 

그러나 여기서 주의해야할 점이 앞에서 예를 들었던 나머지 만큼 one_list에서 사는것보다

 

그냥 6개 패키지를 사는게 더 가격이 쌀 경우가 있는데 이럴 때는 그냥 6개 패키지를 하나 더산다.

 

6개 패키지가 낱개 6개 사는것보다 비싸다면 그냥 전부 다 낱개로 구입하면 된다.