[greedy] 백준 #1049 기타줄

문제

https://www.acmicpc.net/problem/1049

풀이

# 기타줄
n, m = map(int, input().split())

six = []
one = []
for _ in range(m):
    x, y = map(int, input().split())
    six.append(x)
    one.append(y)

price = set([])
num = n // 6
for s in six:
    for o in one:
        for i in range(num+1):
            temp = 6*i
            price.add(s*i + o*(n-temp))
    if n%6 != 0:
        price.add(s*(num+1))

print(sorted(price)[0])

접근

6개 묶음의 가격과 낱개의 묶음을 따로 입력 받는다. 이중for문을 사용해 가능한 모든 경우의 조합을 다 계산하여 set에 넣는다. 중복 제거와 빠른 연산을 위해 set을 사용하였다. n이 6의 배수가 아닌 경우에만 모두 6개 묶음으로 선택하는 경우를 추가해준다. 가능한 모든 경우의 가격들을 정렬하여 가장 적은 값을 출력한다.