[백준] - 다이나믹 프로그래밍 동전 2

동전 2 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

128 MB

52312

15520

10880

28.955%

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

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

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1 복사

3 15
1
5
12

예제 출력 1 복사

3

---

 

다이나믹 알고리즘을 얼마나 손쉽게 푸느냐가 내 알고리즘 머리 아닐까 하는 생각이 들었다. 

 

굉장히 간단해보이는 문제였지만 풀기가 굉장히 까다로웠다. 

문제의 동전 예시는 1, 5, 12 로 굉장히 easy 한 케이스라 조금 더 복잡한 케이스를 생성해서 아이디에이션을 해보았다. 

 

n = 3, k = 20 

2, 5, 12 인 경우, 

 

첫번째로 동전을 채우는 과정을 dfs 로 풀려 했는데 당연히 시간 초과가 났다.

재귀함수로 3곳을 다 방문하도록 했는데 이는 방문 횟수가 너무 많다. 

easy case 에서도 약 7~ 8 배 차이는 난 것 같다. 복잡해질 수록 이 수는 더 증가한다. 

 

다음과 같은 순서로 알고리즘이 작동한다. 

 

위 표는 순서대로 

첫 번째줄: index 

두 번째줄: coin 2 

세 번째줄: coin 5 

네 번째줄: coin 12 이다. 

 

먼저 동전을 채우는 방식이다. 

기존에 나는 동전을 채울 때 

if index % coin == 0

와 같이 나눠서 0으로 떨어지는 경우를 확인하도록 했는데 이렇게 접근해서는 지금 알고리즘에 도달하기 쉽지 않다. 

 

처음 coin 으로 각 값을 만드는데 필요한 개수를 업데이트를 한다. 

 

그 다음 coin 으로 새롭게 업데이트를 하고 싶다. (이 부분이 골자이다.)

 

예를 들어 coin 2로 먼저 채우고서 5로 새롭게 업데이트를 하면 우리 머리속에서는 

min(coin 2로 채운 값, 5 * x (몇번째 5 coin인가)+ 2 * y(5로 채운 이후 index)) 로 개수를 업데이트 하게 될 것이다.

 

이는 동전의 개수가 늘어나게 되면 그 개수에 따라 더욱 복잡한 문제가 된다. 

 

이와 같이 우리의 원래 상식으로 해결이 안되는 문제들이 어려운 알고리즘 문제라고 생각한다. 

 

이를 해결하기 위해서 dp 문제에서는 업데이트 되는 array 의 값을 사용한다. 

min(coin 2로 채운 값, 5 * x (몇번째 5 coin인가)+ 2 * y(5로 채운 이후 index))  

와 유사한 알고리즘이나, 업데이트 되는 array 의 값을 이용하면 동전이 아무리 여러개여도 가장 최근에 업데이트 한 array 값을 사용하기에 array 에 작성된 최소 값에만 집중하면 된다. 

 

이를 구현하기 위해서는 array 값만을 이용해서 coin 개수를 업데이트 할 수 있어야 한다. 

이 구현이 바로 아래와 같다. 

dp[j] = min(dp[j - coin[i-1]] + 1, dp[j])

array 에는 현재 가능한 최소 값이 기입되어 있으므로 여기서 coin 의 크기만큼 1개를 더해준 것과, 원래 array 에 기입되어 있던 최소 개수를 비교하면 어떤 것이 최소 개수 인지 알 수 있다. 

 

알고보면 어렵지는 않지만 우리 삶에서 찾아볼 수 없는 형태이기에 떠올리기 어려운 알고리즘 이었다. 

 

물론 min 으로 업데이트 해야 하기에 초기 값은 큰 수로 설정해야 하고 array 의 첫 index 값만 0으로 설정해줘야

dp[index - coin 크기] + 1

 이 가능하다.

 

또한 각 coin 의 크기에 따라 dp 에 접근하는 index 의 초기값을 coin 의 크기로 설정해줘야 한다. 

 

최종 구현은 아래와 같다. 

import sys 
input = sys.stdin.readline 

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

coin = [0] * n
for i in range(n): coin[i] = int(input())
dp = [10001] * (k+1)
dp[0] = 0

for i in range(1, n+1):
    for j in range(coin[i-1], k+1):
        cnt+=1 
        dp[j] = min(dp[j - coin[i-1]] + 1, dp[j]) 

print(dp[k] if dp[k] != 10001 else -1)