[Python] 백준 온라인 저지 2294번

실버 1 https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.

그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

 

 

[Python]

 

풀이 방법:

 

2293번과 차이점은 사용하는 동전을 최소로 잡는 것

 

필요 요소

1. 코인을 담을 1차원 배열
2. 각 값마다 필요한 최소의 코인 갯수를 저장할 dp 배열

과정

1. 데이터들을 1차원 배열에 담는다
2. 최소 코인 갯수를 저장할 dp배열을 만들고 max(10001)으로 초기화시켜준다.
3. 코인 배열의 값을 가져오고
4. 그 값만큼 올리면서 for문을 돌아주는데
5. 현재 값에서 가져온 코인 값을 빼주었을 때의 코인 사용 개수에 지금 코인 개수 하나를 더한 값과 이전 코인들로만 조합했을 때 사용된 코인 개수를 비교하여 더 작은 값을 dp배열에 담는다

 

 

코드:

n, k = map(int, input().split())
c = [int(input()) for i in range(n)] # 코인의 종류

dp = [10001] * (k+1)
dp[0] = 0

for num in c:
   for i in range(num, k+1):
       dp[i] = min(dp[i],dp[i-num]+1)
       
if dp[k] == 10001:
   print(-1)
else:
   print(dp[k])

 

 

 

 

추가 예정 - [Javascript]

풀이 방법:

정답: