목표 금액을 가장 적은 수의 동전으로 만들려 합니다. 큰 동전부터 고르는 방법이 항상 맞는지 어떻게 판단하며, 동적 계획법과 분할 정복은 어떤 점이 다른가요?

동전 문제에서 큰 동전부터 고르는 탐욕법이 항상 맞는지는 동전 체계의 성질을 증명해야 판단할 수 있습니다. 동전이 1, 3, 4이고 금액이 6이면 탐욕법은 4+1+1인 세 개를 고르지만 최적은 3+3인 두 개이므로 일반적으로는 실패합니다. 금액별 최소 동전 수처럼 같은 부분 문제가 반복되고 이전 결과가 큰 문제에 재사용되면 동적 계획법을 선택하고, 부분 문제들이 독립적이면 분할 정복을 검토하겠습니다.

탐욕의 정당화와 DP 상태를 검증합니다

분할 정복은 문제를 작은 독립 문제로 나눠 각각 해결한 뒤 결과를 합칩니다. 같은 부분 문제가 반복되면 단순 재귀는 같은 계산을 여러 번 합니다. 동적 계획법은 그 결과를 메모하거나 표에 기록해 한 번만 계산합니다. 탐욕법은 현재 단계에서 가장 좋아 보이는 선택을 하고 이후 선택을 되돌리지 않습니다. 이 차이를 최적 부분 구조(optimal substructure)와 중복 부분 문제(overlapping subproblems)의 존재로 설명할 수 있습니다.

금액 x의 최소 동전 수를 best[x]에 저장하면 각 동전 c에 대해 best[x] = min(best[x-c] + 1)을 계산할 수 있습니다. 동전이 x보다 작거나 같은 경우만 살피고, 만들 수 없는 금액은 무한대 같은 표식으로 둡니다. 동전 개수 제한, 각 동전의 사용 횟수, 정확히 금액을 맞출 수 없는 경우가 추가되면 상태와 전이가 달라집니다. 상태에 필요한 정보를 과도하게 넣으면 시간·메모리가 폭증하므로 미래 선택에 영향을 주는 최소 정보만 남깁니다.

탐욕법은 증명이 있을 때만 씁니다

탐욕 선택이 최적 해를 놓치지 않는다는 교환 논증이나 문제 고유의 정규성 조건이 있어야 합니다. 특정 화폐 체계에서 큰 동전 우선이 성립할 수 있어도 임의의 동전 집합에 일반화하면 안 됩니다. 작은 입력을 완전 탐색해 반례를 찾고, 탐욕 결과와 최적 결과를 비교하는 방식으로 먼저 전제를 시험하겠습니다.

DP는 메모이제이션을 붙인 재귀일 수도 있고, 작은 상태부터 채우는 bottom-up일 수도 있습니다. top-down은 실제 필요한 상태만 계산하기 쉽지만 호출 스택과 재귀 오버헤드가 있고, bottom-up은 실행 순서와 메모리 재사용을 통제하기 쉽습니다. 검증은 동전 1이 없는 경우, 큰 금액, 제한된 동전 수, 불가능한 금액을 포함합니다. 빠른 방법보다 최적성의 근거와 상태 정의가 먼저입니다.

동전 DP에서 상태를 금액만으로 둘 수 있는 것은 동전 사용 제한이 없고 각 동전 비용이 한 개라는 전제 덕분입니다. 개수 제한이나 순서가 중요해지면 남은 개수·마지막 선택을 상태에 넣어야 하며 상태 수가 커집니다. 불가능한 값을 큰 수로 표시할 때 +1 오버플로가 나지 않도록 별도 sentinel을 사용하겠습니다.

탐욕 반례를 작은 완전 탐색으로 찾는 것은 일반적인 최적성 증명은 아니지만, 발견 즉시 일반 해법이 아님을 보여 줍니다. DP 결과와 선택 역추적을 기준 구현과 비교하고, top-down의 호출 스택과 bottom-up의 메모리 재사용을 측정합니다. 빠른 코드보다 상태 정의와 선택의 정당화가 먼저입니다.

동전 문제의 점화식은 동전이 무한히 사용 가능하고 목표 금액을 정확히 맞춘다는 조건에서만 그대로 쓸 수 있습니다. 실제로는 금액 범위가 매우 커서 금액별 배열이 불가능할 수 있으므로, 제한된 질의만 계산하거나 다른 상태 압축을 사용해야 합니다. 경로 역추적을 위해 각 금액에서 선택한 동전을 저장하면 메모리가 늘지만 답을 복원할 수 있습니다. 탐욕법이 빠르다는 이유만으로 채택하지 않고, 작은 반례·교환 논증·입력 제약을 함께 확인해 최적성과 자원 예산을 동시에 만족시키겠습니다.

금액 M과 동전 종류 수 C로 정의한 DP는 보통 O(MC) 시간이 듭니다. 입력에 M을 적는 데 필요한 비트 수는 log M이므로 금액 값에 비례하는 이 비용은 입력 비트 길이 기준의 다항 시간이 아니라 의사 다항 시간입니다. 금액이 수십억이면 동전 종류가 적어도 배열 방식이 부적절할 수 있어 최대 금액과 질의 수를 먼저 확인하겠습니다.