[백준/골드5] [2294] 동전2 - python, Pypy 3

부등호

문제내용 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력방식 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

---

프로그래밍 순서

1.dp 리스트 만들기

2.모든 종류의 동전으로 dp 리스트를 모두 돈다.

  2-1 현재 dp 리스트의 값과 현재 동전으로의 값 중 최소가 되는 값으로 업데이트한다.

3. 만약에 dp 리스트의 값이 10001이면 동전으로 해당 가치를 만들 수 없는 것이기 때문에 -1로 변경한다.

---

전체코딩

 

- 코드

# 입력
n, k = map(int, input().split())
data = sorted([int(input()) for _ in range(n)])
 
dp = [10001] * (k+1)
dp[0] = 0
 
# 동전의 최소 개수 구하기
for coin in data:
    for i in range(coin, k+1):
            dp[i] = min(dp[i], dp[i-coin]+1)
            
# 만약 가진 동전으로 k 값이 나오지 않는 경우
if dp[-1] == 10001:
    dp[-1] = -1
    
# 출력 
print(dp[-1])

 

 

---