1. 동전 거스름 돈 N원의 거스름 돈을 돌려줄 때, 최소 개수의 동전을 사용하여 거스름 돈을 돌려주는 방법을 구해보자. 1.1 idea 8월을 거슬러준다고 가정해보면 아래 경우중 하나가 일어날 것이다. 동전은 1원, 4원, 6원짜리가 있다고 가정해보자. 1원 동전 한개 + 7원 최적해 4월 동전 한개 + 4원 최적해 6원 동전 한개 + 2원 최적해 위처럼 작은 사건으로 나눌 수 있다. 식으로 나타내면 아래와 같다. C(i, j)를 크기 Di 동전으로 j원을 거슬러 줄 때의 동전 개수라고 가정하자. C(i, j-Di) + 1 : Di 원을 거슬러 준 경우 동전 하나 추가 C(i-1, j) :거슬러 주지 않고 다음 돈으로 스킵(i원짜리 동전이 없을 때,1원 내기) 2. 바둑 돌 가져가기 완전 정보 게임 :..