[백준] 2294번 동전2 -python 파이썬

문제

 

 

 

이 문제에 대한 해결방법을 계속 고민하다 보면 dp를 사용해 주어야 할 것같은 느낌이 온다.

이전의 평범한 배낭 문제와 비슷한데 그거보다 쉬운버전이라고 생각해주면 된다

 

 

일단 dp 문제 이기 때문에 점화식을 세워 주어야 하는데 우리가 구해야하는 것은 최소가 되는 동전의 개수라는 것을 명심해서

이것을 기준으로 dp를 작성해주면 된다.

 

 

일단dp를 초기 설정할 때 k가 10000이하 이므로 가장 많은 동전의 개수인 10001로 초기화 해주거나 양의 무한대로 값을 설정해주어도 된다.

 

그리고 원소의 개수는 k+1로 해주면 된다. 왜냐하면 가치가 i 일때 최소가 되는 동전의 개수를 구해줄 것이므로 k가치 까지의 dp를 구해주면 되기 때문이다.

 

inf = float('inf')
dp = [inf] * (k+1)

 

 

 

그리고 점화식을 세우는 데 dp[i] 즉,  i 가치일 때 최소가 되는 동전의 개수이다. 

문제에 주어진 예시로 설명해보자면

 

dp[1] = 1 일때 dp[6] = min(1원짜리동전 1개 + 1원짜리동전5개의 총 동전 개수 ,1원짜리 동전 1개 + 5원짜리 동전 1개의 총 동전 개수) 이렇게 된다는 것을 알 수 있다.

이를 식으로 정리 하면 dp[i] = min(dp[i],dp[i-현재코인의 가치]+1)

 

 

전체코드

n, k =map(int, input().split())
coins = [int(input()) for _ in range(n)]
#중복 제거
coins = list(set(coins))
coins.sort()
inf = float('inf')
dp = [inf] * (k+1)
dp[0] = 0

for c in coins:
    #현재 동전보다 작은 값은 갱신되지 않으므로 현재 동전의 값부터 시작
    for i in range(c,k+1):
        dp[i] = min(dp[i],dp[i-c]+1)



#불가능한 경우
if dp[k]>10000:
    print(-1)
else:
    print(dp[k])