[알고리즘] 백준 1049 파이썬 - 기타줄

 

1049번: 기타줄

문제

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

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

 

 

 

문제풀이

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
arr=[]
arr2=[]
#01
for i in range(m):
    a,b=map(int,input().split())
    arr.append(a)
    arr2.append(b)
arr.sort()
arr2.sort()
#02
if(arr[0]>=arr2[0]*6):
    print(n*arr2[0])
#03
else:
    x=n//6
    y=n%6
    if(arr[0]<arr2[0]*y):
        x=x+1
        print(x*arr[0])
    else:
        print(x*arr[0]+y*arr2[0])

- #01 : 입력받은 값을 각가 a와b로 나누어 arr, arr2에 저장 후 오름차순 정렬한다.

- #02 : 만약 arr[0] 값 즉 기타줄 6개 값 중 가장 낮은 값이 기타줄 1개의 가장 낮은 값*6보다

           비싸다면 기타줄을 1개로 여러 개 사는 것이 가장 저렴하기에 "n*arr2[0]"이 답이 된다.

- #03 : 그것이 아니라면 x에 n을 6으로 나눈 몫, y에는 n을 6으로 나눈 나머지를 저장한다.

           이후 arr[0] 값이 arr2[0]*y보다 싸다면 차라리 개수는 넘쳐도 arr[0]을 하나 더 사는 것이 싸다.

           그래서 x를 하나 더 사고 "x*arr[0]"을 출력한다.

           그렇지 않다면 "x*arr[0]+y*arr2[0]"을 출력한다.