[Algorithm] [백준] 1049 - 기타줄 (그리디)

돈을 가장 적게 쓰기!

기타줄이 남더라도 6개 패키지를 사는 것이 낱개보다 싸다면 6개 패키지를 택해야 한다.

1. 가격이 낮은 브랜드를 찾는다.

2. 패키지와 낱개로 나누어 리스트를 만든 후, 오름차순으로 정렬한다.

3. 그러면 패키지 리스트와 낱개 리스트의 인덱스 0번은 가장 싼 물건이 된다.

4. 패키지와 낱개로 6개 중 무엇이 싼지 비교한다.

   4-1. 패키지가 더 싼 경우, 패키지를 사야하기 때문에 몫으로 패키지를 사고 나머지로 낱개를 산다.

   • 여기서 한 번 더 조건문을 걸어줘야 하는데, if ((p+1)*pack_list[0]) < result: 이 부분이다. n에 딱 맞게 사지 않아도(줄이 남더라도) "패키지+낱개" 보다 "패키지+1" 만 사는 것이 더 싸다면 "패키지+1"를 택한다.

   4-2. 낱개 6개가 더 싼 경우, n을 낱개로만 산다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())  # 끊어진 줄의 개수 n과 브랜드 m개

pack_list = []
one_list = []
for _ in range(m):
    a, b = map(int, input().split())  # 패키지 가격 a와 낱개 가격 b
    pack_list.append(a)
    one_list.append(b)

pack_list.sort()  # 인덱스 0이 패키지 가격이 가장 싸다.
one_list.sort()  # 인덱스 0이 낱개 가격이 가장 싸다.

result = 0
if pack_list[0] <= one_list[0]*6:
    p = n//6
    last = n%6
    result = (p*pack_list[0]) + (last*one_list[0])
    if ((p+1)*pack_list[0]) < result:
        result = (p+1)*pack_list[0]
else:
    result = one_list[0]*n

print(result)