백준 - [Silver 1] 2294번 동전 2

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

2294번: 동전 2

---

문제 설명

- n: 동전의 가짓수, k: 만들고자 하는 수

- k를 만들기 위한 동전의 최소 개수 (중복 가능)

- ex)

• n = 3 [1, 5, 12]  ,  k =15  일 때, 15를 만드는 동전의 최소 개수는 4개(12, 1, 1, 1)가 아닌 3개(5, 5, 5)입나다.

---

풀이

- Dynamic Programming(동적 계획법)을 활용해야 한다.

- dp[j] = j를 만들기 위한 동전의 최소 개수

1. dp배열을 최댓값(10001)을 넣은채로 k+1의 길이로 선언한다.
2. 동전의 종류 만큼 루프를 돈다.
3. 동전 액수 ~ k 까지 루프를 돈다.
4. 루프를 돌며 dp 배열에 동전의 최소 개수를 계속 업데이트 해준다. 점화식: min(dp[j], dp[j - i] + 1)

dp는 풀어도 풀어도 어려운 것 같습니다. 문제를 보고 잘 떠오르지 않네요. 코드를 보여주고 진행된 스크린샷을 보며 다시한번 설명드리겠습니다.

 

코드

from sys import stdin
stdin = open("input.txt", "r")
# 숫자 입력
n, k = map(int, stdin.readline().split())

# 입력 받고 중복 제거후 정렬
coins = [int(stdin.readline()) for _ in range(n)]
coins = list(set(coins))
coins.sort()

# dp배열 선언 최대값(10001)
dp = [10001] * (k+1)
dp[0] = 0

# 1, 5, 12원 loop
for i in coins:
    # ex) 5원 차례면 5, 15 까지 loop
    for j in range(i, k+1):
        # dp[j] = 기존 값 / dp[j - i] + 1 = 이전에 만들 수 있는 값 + 1
        dp[j] = min(dp[j], dp[j - i] + 1)

# 값을 못 만들경우 처리
if dp[k] == 10001: print(-1)
else: print(dp[k])

스크린샷

1. 맨 위의 배열은 처음 선언한 값

2. 2번째 출력은 동전이 1일 때 k = 1 ~ 15까지의 동전의 개수 => 15를 만들기 위해 15개 필요

3. 3번째 출력은 동전이 5일 때 k=5일때 1로 바뀐 것을 확인

• 5일때 min(dp[5]=5, dp[5-5]+1=1) 이여서 1로 변환 된 것입니다.
• 15일때 min(dp[15]=15, dp[15-5] + 1 = 3) 이여서 k=15일 때 값이 3으로 변환 됨

4. 마지막 출력에는 동전이 12일때 k = 15인 경우를 확인

• 15일 때 min(dp[15]=3, dp[15-12]+1=4) 이므로 기존의 5일 때 만들었던 값이 선택 됨

위와 같이 문제를 dp를 통해 해결하였습니다. 감사합니다.

 

코드: https://github.com/smothly/Algorithm_Solving/blob/master/boj-2294.py