코드

# n : 동전 개수, k : 만들고자 하는 금액
n, k = map(int, input().split())

# 동전의 종류
coin = [int(input()) for _ in range(n)]

# 만들고자 하는 금액보다 큰 금액은 쓸 수가 없으므로 제외
coin = [x for x in coin if x <= k]
coin = sorted(coin, reverse=True)

# 동전의 최소 개수
cnt = 0

for c in coin:
    cnt += k // c
    
    k = k % c
    
    if k == 0:
        break
        
print(cnt)

문제 해설

그리디 알고리즘 참고

그리디 알고리즘의 가장 기본적인 문제이다. 처음 문제를 똑바로 읽지 않았을 때 DP 문제라고 생각했으나

1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수

위의 조건을 토대로 그리디 문제라는 것을 파악하였다. 가지고 있는 동전의 가치가 모두 배수 관계이기 때문에 가장 큰 값부터 차례대로 넣어주면 최소 개수를 구할 수 있다. 이때 원하는 값인 K원보다 더 큰 금액의 동전은 쓸모가 없기 때문에 제외해야 한다.

댓글남기기

참고