[SWEA DP] 실전문제2 - 완전정보 게임

이 게시글은 SW Expert Academy의 「SW 문제해결 심화 - 동적계획법」 강좌를 바탕으로 작성되었습니다.1. 바둑돌 가져가기 1 초기 : 바둑돌이 K개 있다.

동작 : 자신의 차례에 1개, 3개, 4개의 돌을 가져갈 수 있다. 승부 : 자신의 차례의 동작을 할 수 없으면 그 사람이 패자(loser)가 된다.

부분문제 W(i) : 돌의 개수가 i개일 때, 이기는 방법이 있는 사람 기저조건 : 돌의 개수가 1, 3, 또는 4개라면 F(선수)가 항상 이길 수 있다.주어진 i개의 돌에 대해 F가 돌을 1, 3, 또는 4개를 가지고 간 후,남은 바둑돌에 대한 바둑돌 게임 W(i-1), W(i-3), W(i-4)에 대해서S(후수)가 이기는 방법이 하나라도 있다면 W(i) = F이다..........