Memoization 도입을 통한 Coin Change 시간 복잡도 O(N^Amount)에서 O(N*Amount)로 최적화

Context

모든 가능한 동전 조합을 탐색하는 Brute Force 방식의 재귀 구조 설계. 동일한 하위 문제(Subproblem)의 반복 계산으로 인한 지수 함수적 시간 복잡도 증가와 성능 저하 발생.

Technical Solution

• 중복 계산 제거를 위해 계산된 최적값을 저장하는 Memoization 구조 도입
• target 금액을 State로 정의하여 각 상태별 최소 동전 개수를 저장하는 dp 배열 설계
• 모든 동전 종류를 순회하며 1 + solve(target - coin)의 최솟값을 선택하는 State Transition 로직 구현
• 기저 사례(Base Case) 설정을 통한 재귀 종료 조건 및 불가능한 금액에 대한 예외 처리
• Top-Down 방식으로 상위 문제부터 하위 문제로 분할하여 필요한 상태만 계산하는 효율적 탐색 수행