[백준] 2294번 : 동전 2

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

2294번: 동전 2

다이나믹 프로그래밍으로 해당 문제를 해결 하였습니다. 가치가 같은 동전이 있을 수 있기때문에  집합 자료구조를 이용하여 중복을 입력을 방지하였고, 동전을 작은 순서부터 순회하기위하여 정렬하였습니다. 이후 동전을 작은 순서부터 dp테이블을 순회하며 dp 테이블을 초기화 합니다. dp 점화식은 아래와 같이 정의 할 수 있습니다.

i 인덱스를 코인으로 나눈 나머지가 0인경우 그렇지 않은경우로 두가지로 나누었습니다.

i 인덱스를 코인으로 나눈 나머지가 0인경우는 해당 코인으로 i 인덱스의 최소 동전 개수(i나누기coin)를 구할 수 있습니다.

그렇지 않은 경우에는 현재 자기자신에서 이전에 있던 dp테이블에서 자기자신의 동전을 추가한 값(i-coin)을 최소값으로 넣습니다.

따라서 다음과 같이 코드로 작성 할 수 있습니다.

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

for _ in range(n):
    coin.add(int(input()))
    
newcoin = sorted(coin)

INF = int(10e9)
dp = [INF for _ in range(k+1)]

for coin in newcoin:
    for i in range(1, len(dp)):
        if i % coin == 0:
            dp[i] = min(dp[i], i // coin)
        else:
            if i-coin > 0: # 인덱스 에러
                dp[i] = min(dp[i], dp[i-coin] + 1)
            
if dp[k] == INF:
    print(-1)
else:
    print(dp[k])