동전 문제

문제에 대한 설명은 problem.pdf 참조.

 

input.txt에 있는 데이터를 파이프 입력으로 주어 output과 같은 답을 얻어야 한다.

input.txt

output.txt

problem.pdf

coin3.cpp

source.rar

★ 풀이

 

예를 들어 동전이 10원, 50원, 100원이 있습니다. 이 동전을 사용하여 1000원을 맞추는 경우의 수를 생각해봅시다.

 

첫째로 100원을 쓰고, 나머지 900원을 10원 / 50원 / 100원으로 조합하는 방법이 있을 것입니다.

둘째로 100원을 쓰지 않고, 1000원을 10원 / 50원으로 조합하는 방법이 있을 것입니다.

 

위 둘은 경우가 다르므로(사용하는 동전의 개수가 달라져 다른 경우가 됩니다), 더해서 올바른 조합 회수를 얻을 수 있습니다.

첫째 값은 이렇게 구할 수 있습니다. 900원에 대한 조합 회수를 가져오는 것이지요. 그럼 900원에 대한 조합 회수는 어떻게 가져올까요. 이것 역시 100원을 쓰고 나머지 800원을 10원 / 50원 / 100원으로 조합하는 방법, 100원을 쓰지 않고 900원을 10원 / 50원으로 조합하는 방법을 가져와 둘을 더합니다. 이는 재귀 연산이 됨을 알 수 있습니다.

 

둘째 값은 이렇게 구할 수 있습니다. 이전에 조사한, 즉 10원 / 50원으로 1000원에 대한 조합 회수를 헤아린 것을 가져오는 것이지요. 그럼 10원 / 50원으로 조사한 1000원에 대한 값은 어떻게 가져왔을까요. 마찬가지로 10원으로 조사한 1000원에 대한 값을 가져옵니다. 이 또한 재귀 연산이 됩니다.

 

쉽게 하려면, 일단 10원에 대한 경우의 수를 조사해놓은 후 시작합니다. 이제 50원을 쓰는 경우에 이르면 위에 설명한 방법을 사용합니다. 100원 시점을 예로 들겠습니다. 이 때는 50원을 쓰고 남은 50원의 경우의 수와 10원 만을 쓴 100원에 대한 경우의 수를 더해서 구합니다.

 

식은 다음과 같이 나타납니다.

 

 

조합 회수 = 함수 ( 현재 단계 , 액면 - 현재 선택된 동전 ) + 함수 ( 이전 단계 , 액면 )

 

※ 단계는 그 시점에서 선택 가능한 동전 종류를 뜻합니다.

 

 

이번에 몇 가지 얻은 점이 있습니다. 동적 프로그래밍은 단계 즉, 이전에 구한 최적의 값과 현재 상태를 언제 사용할지 판단하는 것이 중요한 것 같습니다.