[백준] 2294 동전 2 Python (DP문제)

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

2294번: 동전 2

크게 두가지 경우로 생각하여 풀었다 ~

INF = int(1e9)
dp = [INF]*(k+1)

우선 dp를 최대값으로 초기화 시켜준다! 사용하는 동전의 최소개수를 찾기 위해 계속 for문을 돌면서 갱신해줄 예정이므로 int(1e9) 값으로 초기화 해주었다. 

i) 동전과 현재 검사중인 금액 money 가 같으면 , 동전 하나로 해당 금액을 만들 수 있으므로 dp[money] = 1

if coin == money:
    dp[money] = 1

ii) 동전 단위가 우선 money 보다 작은지 확인한다 

기존의 dp[money] 에 저장되어 있는 동전 개수와 현재 동전을 선택하는 경우 동전개수를 비교하여 더 작은 값을 dp[money]에 저장한다 

dp[money] = min(dp[money-coin]+1, dp[money])

# 2294 동전 2
n, k = map(int, input().split())
coins = []
for _ in range(n):
    c = int(input())
    if c not in coins:
        coins.append(c)

INF = int(1e9)
dp = [INF]*(k+1)

for money in range(1, k+1):
    for coin in coins:
        if coin == money:
            dp[money] = 1
        elif coin < money:
            dp[money] = min(dp[money-coin]+1, dp[money])
if dp[k] == INF:
    print(-1)
else:
    print(dp[k])

dp...문제 그래도 이건 풀었다 ㅎㅎ