동전 종류가 담긴 리스트와 목표 금액(amount)이 주어졌을 때, 이 동전들을 조합하여 목표 금액을 정확히 만들 수 있는 조합의 개수를 구하는 문제입니다. 만약 결과값이 매우 크다면 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어, 입력이 coins = [2, 5], amount = 10이라면 출력은 2가 됩니다. 다음과 같은 두 가지 조합으로 10을 만들 수 있기 때문입니다.
- [2, 2, 2, 2, 2]
- [5, 5]
문제 해결 접근 방식
이 문제는 대표적인 동적 계획법(Dynamic Programming) 유형으로 풀 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 모듈로 값 m := 10^9 + 7을 설정합니다.
- 크기가 amount + 1인 dp 리스트를 생성하고 모든 값을 0으로 초기화합니다.
- dp[0] := 1로 설정합니다. (금액 0을 만드는 방법은 아무것도 선택하지 않는 한 가지뿐이기 때문입니다.)
- 각 동전 d에 대해 다음을 반복합니다.
- i를 1부터 dp의 크기까지 순회하면서,
- i - d >= 0이면 dp[i] := dp[i] + dp[i - d]로 갱신합니다.
- 마지막으로 dp의 마지막 원소를 m으로 나눈 나머지를 반환합니다.
여기서 중요한 점은 동전을 바깥 루프에서 순회한다는 것입니다. 이렇게 하면 [2, 5]와 [5, 2]처럼 순서만 다른 중복 조합이 카운트되는 것을 방지할 수 있습니다.
구현 예시
class Solution:
def solve(self, coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1
for d in coins:
for i in range(1, len(dp)):
if i - d >= 0:
dp[i] += dp[i - d]
return dp[-1] % (10 ** 9 + 7)
ob = Solution()
coins = [2, 5]
amount = 10
print(ob.solve(coins, amount))
입력
[2, 5], 10
출력
2
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(len(coins) × amount), 공간 복잡도는 O(amount)입니다. 동전의 개수와 목표 금액에 비례하여 선형적으로 증가하므로, 상당히 큰 입력에도 효율적으로 동작합니다.