BOJ 동전0

1. BOJ 11047 동전0

난이도 : 실버3, 그리디 (하지만 DP로 풀었다)

관련 문제 : 설탕배달 (그리디), 동전1 (DP)

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

코드

n, k = map(int, input().split())
A, rm = [], []
dp = [0 for _ in range(n)]
 
for i in range(n):
    rm.append(int(input()))
 
for i in rm:
    if i<=k:
        A.append(i)
 
dp[0] = k
 
for i in range(1, len(A)):
    x = A[i]//A[i-1]
    if dp[i-1]%x==0:
        dp[i] = dp[i-1]//x
        dp[i-1] = 0
    else :
        dp[i] = dp[i-1]//x
        dp[i-1] = dp[i-1]%x
 
print(sum(dp))

N 종류의 동전으로 K원을 만들 때, 동전 개수의 최솟값을 구하는 문제이다. 

이 문제에서 주의할 점은, 동전이 1부터 오름차순으로 주어지는데, (1 , 5, 10, 50 ...) 처럼 A[i]이 A[i-1]의 배수가 된다. 

A[0]은 무조건 1이다. 

1. A, rm은 동전 종류를 저장하는 리스트이다.
rm으로 우선 입력 값을 받아온 후 동전 중에 값이 k이상인 것은 빼고 A로 저장한다. 
A가 최종 동전 리스트이다. dp는 각 동전의 개수이다. 

2. A[0] = 1 이므로, k원을 만들기 위해 1원 k개가 필요하다. 따라서 dp[0] = k 이다. 

3. 1부터 A까지 for문을 돌면서 dp 리스트를 업데이트 해줄 것이다. 

4. A[i]는 A[i-1]의 x 배이다. 

예를 들어, A[1] = 5원이라면 4200원을 만들기 위해 4200/5인 840개가 필요하다. 
이 경우 A[1]이 A[0]를 전부 대체할 수 있다. 따라서 dp[i] = dp[i]//x 이고, dp[i-1] = 0으로 업데이트한다. 
만약 4202원이었다면, x는 2만큼의 나머지가 생긴다.
이때는 A[1]은 420개, A[0]는 2개를 사용해야할 것이다. 따라서 dp[i] = dp[i]//x 이고, dp[i-1] = dp[i]%x 로 업데이트한다.