정의

동전 조합 문제는 주어진 동전 종류로 목표 금액을 만드는 방법의 수를 구하는 알고리즘입니다. 순서는 상관없이 조합만 셉니다.

핵심 특성

• ✓dp[i] = 금액 i를 만드는 조합의 수
• ✓동전을 외부 루프로 → 조합만 셈 (순열 아님)
• ✓dp[0] = 1 (아무것도 안 고르는 1가지)
• ✓점화식: dp[i] += dp[i - coin]

시간 복잡도