백준_DP_동전2_2294_파이썬

✅문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

ㅤ

✅입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

✅출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

✅ 알고리즘 분류

• 다이나믹 프로그래밍

💡풀이

알고리즘 풀 때 웬만하면 분류를 안보고 풀어보고, 안풀리면 보도록 하는 편이다.
처음에 백트레킹이겟지 하고 열심히 작성하는데 풀면서 백트레킹으로 한계가 점점 보여서 아닌 것 같다고 고민고민 했는데 결국 DP여서 망설임 없이 다 지웠다 🤦‍♂️
결국 memoization 방법을 고민하다가 생각한 아이디어

크기가 K+1인 memoization 배열 생성
크기가 작은 동전coin부터 for문으로 차례대로 memoization을 탐색을 한다

1. 임의 값 value-coin를 만들 수 있는 동전 조합이 있을 때
   1) value-coin 를 만들 수 있는 경우의 수에서 coin 1개를 더하면 되니
   배열의 value-coin 인덱스에서 동전 수 1개 추가: memoizaion[value-coin] + 1
2. 임의 값 value-coin를 만들 수 있는 동전 조합이 없을 때
   pass
3. 다음 coin으로 memoization 재탐색
4. 최종적으로 인덱스 번호 K 의 값을 출력하면 답!

정답 풀이

N, K = map(int, input().split())        # N가지 동전, 목표 15원
coins = list({int(input()) for _ in range(N)})

memo = [K+1]*(K+1)                      # memoization 배열 (K+1은 만들지 못할 때 임의의 큰 수를 담은 것)
memo[0] = 0                             # 0원은 만들 수 없으니 0

for coin in coins:                      # 동전 탐색
    for i in range(coin, K+1):          # 배열 탐색
        if memo[i-coin] != K+1:         # 현재 값-동전의 배열 값이 있으면 갱신
            memo[i] = min(memo[i], memo[i-coin]+1)

print(memo[K] if memo[K]!=K+1 else -1)

📌 배운 점

이것이 코딩 테스트다 를 정독해서 풀 수 있었던 문제..(광고아님)
DP는 근데 memo아이디어 떠올리기가 정말 쉽지않다. 점화식을 세우는 게 보통일이 아님
자주 푸는 게 가장 중요한 파트!