동전 거스름돈 구하기(전체탐색으로)

동전 거스름돈을 계산 하는 문제는 일반적으로 DP를 이용해서 구하게 됩니다.
여기저기 DP 설명만 있어서, 여기에서는 전체 탐색을 어떤 식으로 하는지에 대한 설명를 하도록 하겠습니다.

[질문] 아래 동전 종류가 있을때 최소의 거스름돈 갯수는 몇개일까?
동전 종류:1원,5원,10원,16원
거스름돈:20원

일반적으로 접근을 하자면 부분집합,순열,조합 3가지중에 하나라고 생각하면 됩니다.

순열은

집합에서 순서가 다르게 끄집에 내는 경우, 1,5,10,16 이란 집합에서 1,5,10,16, 과 5,1,10,16 ??? 이런식으로 순서를 바꿔서 꺼내는 가지수가 다른경우로 인식하기 때문에 해당문제와는 관계가 없습니다.

다음으로 조합

의 경우 순서에는 관계가 없으므로 4C2 라고 하면 4개중에 2개를 고르는 방법이 됩니다. 4C1 이면 4개 중에 1개를 고르는 방법이고요, 최종 결과 20이 되려면 몇개를 골라야할지 모르기 때문에 조합 문제도 아닙니다.

마지막으로 

남은 부분집합은 몇개를 골라서 집합을 만드는겁니다. 1,5 고르고 1,10,16도 골라보고... 이게 20원이 되는지 보는 겁니다.

여기에도 문제는 있습니다. 

동전 종류가 하나씩만 쓸 수 있으면 부분 집합 문제일 수 있는데 5,5,5,5,5 등으로 무한정으로 사용할 수 있기 때문입니다.
다시 문제로 돌아가서 1,1,1,1,1,1,5,5,5,5,5,5,10,10,10,10,10,16,16 이런식으로 많다고 문제를 바꿔 놓고 문제를 풀면 될 것입니다.

DP쪽에서 점화식을 나타내는 방법이 있는데 그러한 방법을 이용해서 재귀 호출로 푸는 방법이 있는데 그건 여기에서 언급하지 않도록 하겠습니다.

동전은 임으로 배치하였습니다. 호출 되는 관계는 아래 그림을 참고 하면 됩니다.

아래는 구현 코드 입니다. subset1은 가지치기 없이 순수하게 일치하는 구간을 나타냅니다.
subset2는 가치치기를 통해 불필요한 node로의 진입은 하지 않도록 합니다.
여기서 눈여겨 볼 소스 코드는 starti인자 입니다. 해당 값을 현재의 i값을 넘김으로서 중복을 허용하도록 합니다. 즉 1을 선택중이라면 1을 계속 선택할수 있게 합니다. 만약 i+1을 넘기면 1 다음에 인자 10 부터 선택하겠다는 의미가 되어서 중복 선택을 하지 못하게 됩니다.

C, pasted just now: 

#include <stdio.h> int data[10] = {16,1,10,5}; int sel[100]; int selcount = 0; int N = 4; int P = 20; int subset1(int depth,int starti, int sum) { int i; if( sum > P ){ return 0; } if( sum == P ){ for(i=0;i<selcount;i++){ printf("%d ",sel[i]); } printf("\n"); return 0; } for(i=starti;i<N;i++){ sel[selcount] = data[i]; sum = sum + data[i]; selcount++; subset1(depth+1,i,sum); selcount--; sum = sum - data[i]; } return 0; } int mincount = 10000; int subset2(int depth,int starti, int sum) { int i; if( sum > P || mincount <= selcount){ return 0; } if( sum == P ){ for(i=0;i<selcount;i++){ printf("%d ",sel[i]); } printf("\n"); mincount = selcount; return 0; } for(i=starti;i<N;i++){ sel[selcount] = data[i]; sum = sum + data[i]; selcount++; subset2(depth+1,i,sum); selcount--; sum = sum - data[i]; } return 0; } int main() { printf("subset1\n"); subset1(0,0,0); printf("subset2\n"); subset2(0,0,0); return 0; }

Output:

subset1 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 5 5 1 1 1 1 1 10 5 1 1 1 1 1 5 5 5 10 10 10 5 5 5 5 5 5 subset2 16 1 1 1 1 10 10