[백준] 1049 : 기타줄 - Python

그리디 알고리즘

문제풀이
패키지, 낱개 따로 정렬해서 풀었다면 굉장히 쉽게 풀 수 있었을 것.

생각
가장 먼저 낱개로 사는게 패키지로 사는 것보다 싼지를 생각한 후 그게 아니라면 패키지만큼을 먼저 산 후에 남은 개수를 낱개로 살지 패키지로 살지를 정하는 코드로 짰다면 굉장히 간단하게 풀 수 있었을 것.

소스코드

import sys



N, M = map(int, input().split())
pack = []
one = []

for i in range(M):
    p, o = map(int, input().split())
    pack.append(p)
    one.append(o)

#N개를 다시 사야함
pack.sort()
one.sort()    # 둘다 오름차순으로 ..
min_pack = pack[0]
min_one = one[0]

res = 0
if min_one * 6 < min_pack:
    res = min_one * N 
else:
    res += min_pack * (N//6)
    #패키지 구매 이후에 남은 낱개 비교
    if min_one * (N%6) < min_pack:
        res += min_one * (N%6)
    else:
        res += min_pack

print(res)