[알고리즘/DP] 2294번 : 동전 2 - python

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

2294번: 동전 2

 

---

• 문제
• 소요시간: 23분 9초

---

• 설계하기(접근방법) 

1. 입력받기

코인을 입력받는다

 

2. 구현하기

이전에 풀어본 dp 문제이다

이전 문제와 다른 점은 동전이 정해지지 않았다는 점이다

 

하지만 set으로 중복되는 동전을 한정짓고

while문으로 작은 동전부터 

dp[n] = dp[n-1] + 1 을 반복한다면

 

최적의 해를 구할 수 있다

이전 동전 0 문제를 참고하자

 

 

3. 출력하기

dp[target]이 10E9라면 불가능(-1) 출력

가능하다면 dp[target]을 출력한다

 

 

---

• 코드(출력)

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

coin_list = []
dp = [10E9] * 10001
dp[0] = 0

for _ in range(n):
    coin = int(input())
    coin_list.append(coin)

coin_list = list(set(coin_list))
coin_list.sort()

for i in coin_list:
    n = i 
    while n <= 10000:
        if dp[n] > dp[n-i] + 1:
            dp[n] =  dp[n-i] + 1
        n += 1



if dp[target] == 10E9:
    print(-1)
else: 
    print(dp[target])

---

• 얻어갈 부분

1. 동전 0 문제를 복습했다