4종류 동전으로 N 센트를 표현하는 경우의 수

1. 문제

쿼터( 25센트 ), 다임( 10센트 ), 니켈( 5센트 ), 페니( 1센트 ) 의 네 가지 동전이 무한히

주어진다고 했을 때, N 센트를 표현하는 모든 경우의 수를 구하라.

 

2. 문제 분석

이 문제는 재귀 문제이다.

함수 makeChange(N)을 부분 문제들의 답을 통해 계산하는 법을 알아내 보도록 하자.

 

N = 100 이라고 해보자.

도합 100 센트의 잔돈을 만드는 방법을 계산해야 한다.

이 문제와 부분 문제들은 어떤 연관성을 가지는가?

100센트의 잔돈에는 쿼터가 0개, 1개, 2개, 3개, 4개 있을 수 있다는 것을 알고 있다.

( 쿼터는 25센트니까, 25 * 5 = 125센트가 되어서, 쿼터는 5개가 될 수 없다. ) 

그러므로,

위의 관계가 성립한다.

이 결과를 좀 더 들여다보면, 문제의 크기를 줄일 수 있는 지점이 있음을 알게 된다.

가령, makeChange( 1개의 쿼터로 100 만듦 ) 은 makeChange( 0개의 쿼터로 75 만듦 ) 과 동일하다.

쿼터 하나가 반드시 들어가야 한다는 것은 알고 있으니,

남은 75센트를 만드는 방법만 알아내면 되기 때문이다.

 

이를 makeChange( 2개의 쿼터로 100 만듦 ), makeChange( 3개의 쿼터로 100 만듦 ),

makeChange( 4개의 쿼터로 100 만듦 ) 에도 적용하면 아래와 같은 결과를 얻는다.

makeChange( 4개의 쿼터로 100 만듦 )은 1이다.

makeChange( 4개의 쿼터로 100 만듦 ) 가 1이 되는 이유는, 

네 개의 쿼터로 100 센트를 만드는 방법은 하나뿐이기 때문이다.

문제 줄이기가 완전히 끝난 경우이다.

 

그러면, 앞으로 뭘해야 하지?

쿼터는 다 썼으니, 다음으로 큰 단위의 동전을 가지고 비슷한 작업을 해야 한다.

다음 동전은 다임이다.

쿼터에 적용했던 접근법을 다임에도 그대로 쓸 수 있지만,

위의 수식 우변의 각 항에 대해 개별적으로 적용해야 한다.

그러므로 아래와 같은 결과를 얻는다.

이 각 각을 다시 확장한 다음에 니켈에 대해서도 똑같이 한다.

결국, 트리와 같은 재귀 호출 구조가 만들어지게 되는데, 한 번의 재귀 호출에 대해 네 번 이상의 재귀 호출이 이루어지게 된다.

이 재귀 호출 알고리즘의 초기 사례는 makeChange( 0쿼터로 50 만듦, 5다임 ) 과 같이 1로 완전히 줄여진 부분 문제들이다.

그 이유는 5다임은 50센트와 같기 때문이다.

 

위의 내용을 그림으로 대강 스케치하면 다음과 같다.

아래는 위의 과정을 트리 구조로 나타낸 것이다.

이는 곧, 재귀함수로 접근하면 된다.

3. 자료구조 정의

위의 4가지 동전은 가장 큰 단위의 동전부터 시작하자.

그리고 동전을 배열로 관리하도록 하자.

그러면, 배열의 길이가 동전의 종류이기 때문에 4가 되며,

배열은 아래와 같이 초기화를 하도록 하자.

위와 같이 동전을 배열로 두면 유용하다.

그 이유는 배열의 0번째 인덱스에는 쿼터동전값, 1번째는 다임동전값, 등을 의미하게 된다.

즉, 프로그램이 처음 시작시에 인덱스는 0번부터 시작을 하도록 설계를 할 수 있다. 

 

4. 구현

프로그램 실행결과

4. 소스 파일

main.c

0.00MB