본 포스팅은 해당 문제를 1차원 배열의 DP로 푼 풀이에 대해 정리하였다.
그러나 그리디로도 쉽게 풀 수 있기 때문에 아래 포스팅도 참고 바란다.
난이도가 올라갈수록 DP는 보통 다른 알고리즘들로 풀 수 없을 때 활용하는 최후의 방안이기 때문에 이 문제를 그리디로 푸는 방법을 모른다면 아래 포스팅을 꼭 공부해보기를 추천한다.
📋 참고 포스팅:[백준/Python] 11047. 동전 0
📄 문제
백준
난이도 : Silver 4
문제 제목 : 동전 0
✏️ 풀이 1
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [0] * (k+1)
dp[0] = 1
for coin in coins:
for i in range(coin, k+1):
dp[i] += dp[i - coin]
print(dp[k])✅ 풀이 한줄 설명:
DP로 풀 수 있는 문제이다. 위 풀이는 DP 테이블을 다음과 같이 정의한 풀이이다.
dp[i] = i원을 만들 때 가능한 동전 조합의 수
✅ 풀이 자세한 설명:
DP 문제는 다음과 같이 풀이를 진행하는 것이 좋다.
- 테이블 정의하기
- 점화식 찾기
- 초기값 정의하기
🍎 1. 테이블 정의하기
dp[i] = i원을 만들 때 가능한 동전 조합의 수
🍎 2. 점화식 찾기
동전 종류를 하나씩 돌면서, 현재 보고 있는 동전을 사용하여 i원을 만드는 경우의 수를 계산하는 식을 찾아보자.
점화식: dp[i] += dp[i - coin]
coin을 사용하여 i원을 만들 수 있는 경우의 수는, 해당 동전만큼을 제외한 값을(i - coin) 만들기 위한 동전 조합 수와 같다.
왜냐하면 i원을 만들 수 있는 경우의 수는 결국 i - coin원을 만들 수 있는 경우들에 coin원 하나를 추가해준 것이기 때문이다.
예를 들어 1원, 2원 동전이 있는 상황에서, 2원 동전을 사용하여 5원을 만들기 위한 경우의 수를 구해보자.
- (1원, 1원, 1원, 1원, 1원)
- (1원, 1원, 1원, 2원)
- (1원, 2원, 2원)
여기서 첫 조합은 2원 동전을 사용하지 않았기 때문에 패스한다. (실제로 코드에서 보면 이미 이 경우는 dp[5]에 더해져 있다.)
결국 두번째, 세번째 조합은 3원을 만들 수 있는 경우에 2원을 더해 5원을 만든 것일뿐이다. 따라서 dp[5] += dp[5 - 2] 를 해주면 된다.
➕ 다른 DP 문제에 비해 이 점화식의 특이점이라고 한다면, coins에 대해 for문을 돌면서 dp[i]가 매번 (현재coin에 대한 반복마다) 다시 갱신된다는 점이다.
🍎 3. 초기값 정의하기
dp[0] = 1
0원을 만드는 동전 조합의 수는 공집합으로 1개이다.
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '12852. 1로 만들기 2'
GitHub - [16강] 시뮬레이션/연습문제 '12852. 1로 만들기 2'
이 풀이는 동전이 다른 동전의 배수라는 조건이 없을 때도 유용하게 사용할 수 있을 것 같다.
만약 이 포스팅을 보고도 이해가 어렵다면, DP의 유명한 유형인 knapsack 문제를 이해한 뒤 보면 조금 더 쉬울 것 같다.
