문제 요약
거슬러 줘야 하는 금액 n과 사용할 수 있는 화폐 단위 money가 주어진다.
각 화폐는 무한히 사용할 수 있으며, n원을 만드는 방법의 수를 구해야 한다.
정답이 커질 수 있으므로 1,000,000,007로 나눈 나머지를 반환한다.
핵심 아이디어
이 문제는 동전으로 특정 금액을 만드는 조합의 수를 구하는 문제다.
중요한 점은 순서가 다른 경우를 다른 방법으로 세면 안 된다는 것이다.
예를 들어 다음 두 경우는 같은 방법이다.
1원 + 2원
2원 + 1원따라서 금액을 기준으로 먼저 탐색하는 것이 아니라, 화폐 단위를 하나씩 고정하면서 DP를 갱신해야 한다.
DP 정의
dp[i]를 다음과 같이 정의한다.
dp[i] = 현재까지 확인한 화폐 단위만 사용해서 i원을 만드는 방법의 수초기값은 다음과 같다.
dp[0] = 10원을 만드는 방법은 아무 동전도 사용하지 않는 1가지 방법으로 본다.
점화식
어떤 화폐 단위가 coin일 때, coin원부터 n원까지 순회한다.
dp[amount] += dp[amount - coin]의미는 다음과 같다.
amount원을 만드는 방법
= 기존 amount원을 만드는 방법
+ coin을 하나 추가해서 amount원을 만드는 방법amount - coin원을 만들 수 있다면, 거기에 coin 하나를 추가해서 amount원을 만들 수 있다.
Python 코드
def solution(n, money):
MOD = 1_000_000_007
dp = [0] * (n + 1)
dp[0] = 1
for coin in money:
for amount in range(coin, n + 1):
dp[amount] = (dp[amount] + dp[amount - coin]) % MOD
return dp[n]코드 설명
dp[0] = 1
아무 화폐도 사용하지 않고 0원을 만드는 경우를 1가지로 둔다.
이 값이 있어야 첫 번째 화폐 단위로 정확히 coin원을 만드는 경우가 계산된다.
dp[coin] += dp[0]화폐 단위 기준 반복
for coin in money:화폐 단위를 하나씩 사용 가능하게 만들면서 경우의 수를 누적한다.
이렇게 하면 같은 조합을 순서만 바꿔서 중복 계산하지 않는다.
금액 기준 반복
for amount in range(coin, n + 1):현재 화폐 coin을 사용할 수 있는 최소 금액부터 n까지 확인한다.
작은 금액에서 큰 금액으로 순회하는 이유는 같은 화폐를 여러 번 사용할 수 있기 때문이다.
나머지 연산
dp[amount] = (dp[amount] + dp[amount - coin]) % MOD경우의 수가 매우 커질 수 있으므로 매번 1,000,000,007로 나눈 나머지를 저장한다.
왜 1차원 DP로 충분할까?
2차원 DP로도 생각할 수 있다.
dp[i][j] = i번째 화폐까지 사용해서 j원을 만드는 방법의 수하지만 현재 행은 이전 계산 결과만 있으면 갱신할 수 있다.
따라서 금액 배열 하나만 사용해도 충분하다.
1차원 DP를 사용하면 공간 복잡도를 줄일 수 있다.
주의할 점
반복문의 순서를 바꾸면 순열을 세게 될 수 있다.
다음과 같이 금액을 바깥 반복문으로 두면 문제가 된다.
for amount in range(1, n + 1):
for coin in money:
...이 방식은 같은 동전 조합이라도 선택 순서가 다르면 다른 경우로 계산될 수 있다.
이 문제는 조합의 개수를 구해야 하므로 반드시 화폐 단위를 바깥 반복문으로 둔다.
시간 복잡도
화폐 단위의 개수를 m이라고 하면, 각 화폐마다 n까지 순회한다.
O(m * n)m은 최대 100, n은 최대 100,000이므로 최대 약 10,000,000번의 연산이 필요하다.
Python으로 충분히 처리할 수 있는 범위다.
공간 복잡도
n + 1 크기의 DP 배열 하나를 사용한다.
O(n)정리
이 문제는 무한히 사용할 수 있는 화폐들로 특정 금액을 만드는 조합 수를 구하는 문제다.
핵심은 다음 두 가지다.
dp[i]를i원을 만드는 방법의 수로 정의한다.- 중복 조합을 피하기 위해 화폐 단위를 바깥 반복문으로 둔다.
이 원리를 사용하면 1차원 DP로 효율적으로 해결할 수 있다.
