알고리즘 스터디 - 백준 2294번 : 동전 2

문제 해석

• n가지 종류의 동전을 사용해 가치의 합이 k원이 되도록하지만 동전의 개수가 최소가 되도록함
• 조합으로 구해야 함

입력

• n, k를 입력 받음
• n개의 줄에 동전의 가치가 주어짐

어떤 알고리즘을 사용해야할까?

3 15
1
5
12

0 - 0
1 - 1
2 - 1, 1
3 - 1, 1, 1
4 - 1, 1, 1, 1
5 - 5
6 - 5, 1
7 - 5, 1, 1
8 - 5, 1, 1, 1

dp[0] = 0
dp[1] = dp[1-1] + 1
dp[2] = dp[2-1] + 1

• 이런 형식으로 했을 때 특정 위치에 있는 DP[i] = min(DP[i-coin]) + 1이다.
• 여기서 최솟값은 모든 coin을 순환하면서 값을 계산하고 특정 리스트에 저장한 후 그 리스트의 최솟값을 의미한다.

알고리즘 코드

n, k = map(int, input().split())

coin = []

DP = [0 for _ in range(k + 1)]

for i in range(n):
    coin.append(int(input()))

for i in range(1, k + 1):
    check = []
    # 각 코인을 순환
    for j in coin:
        # 코인을 순환하면서 불가능하지 않는 경우를 지속적으로 더해나감
        if j <= i and DP[i - j] != -1:
            check.append(DP[i - j])
    
    # 비어있으면 불가능하다는 의미
    if not check:
        DP[i] = -1
    # 비어 있지 않으면 최소 개수 + 1
    else:
        DP[i] = min(check) + 1

print(DP[k])