[ 알고리즘 ] Dynamic Programming : 동전 거스름 돈, 바둑 돌 가져가기

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. 바둑 돌 가져가기

 

완전 정보 게임 : 게임의 정보가 참가자 모두에게 공개된 게임. 누가 먼저하는가에 따라 승부가 결정나있음

ex) 화투, 포커, 스포츠베팅

 

바둑돌 가져가기도 그 예시 중 하나이다. 

규칙은 아래와 같다.

바둑돌이 k개가 있고 두 사람이 번갈아가며 자신의 차례에 1개 혹은 두개의 돌을 가져갈 수 있다. 

자신의 차례에 동작을 할 수 없으면 그 사람이 진다.

 

반드시 이긴다와 반드시 진다는 비슷해보이지만 의미가 살짝 다르다.

반드시 이긴다는 내가 이 행위를 하면 상대방이 뭔하던 이길 수 있다이지만

반드시 진다는 내가 뭘해도 진다는 의미이다. 

 

2.1 idea

 

남아있는 돌의 개수가 i개일 때 이기는 경우가 있을 때 Di는 O를 갖고 없으면 X를 취한다.

i	0	1	2	3	4	5	6	7	8
나	X	O	O	X	O	O	X	O	O

i가 3일 경우 지는 이유는 내가 하나 골랐을 때 상대방을 i=2로 보내고 내가 두개를 골랐을 때는 i=1로 보내기 때문이다.

i가 1이거나 2일 때는 Di가 O이므로 상대방이 이기게된다.

 

i가 4일 때는 내가 하나를 골라 상대방을 i가 3일 때로 보내면 승리할 수 있다.

 

i가 6일때도 상대방을 i가 4일 때와 5일 때로 보내기 때문에 상대방이 이게게된다.