[수업]Coin Game

Intro..

이 문제는 Nim게임 + DP 관련 문제이다.

Nim게임 + DP 관련해서 정리해둔 게시글이 있기 때문에 참고할 것.

문제

풀이

Nim게임의 한 종류로 필승전략게임에서 파생된 문제이다.
DP방식과 규칙찾아서 구하는 방식이 있다.
총 2가지 방법이 있다는 의미이다.

문제 참고 : 1~3코인 가져갈수있고, 3개 병이있다.

2-1) DP

• d(6,7,8)의 경우 3개3개3개까지 경우는 9가지다
  • 참고로 d(7,8,6)이런거랑 d(6,7,8)은 같으니 한 케이스로 봄)

• 이 9가지를 컴퓨터가 전부 승하면, 자신은 패배.

• 다만, 1가지라도 컴퓨터가 패하면, 내가 이길방법이 1가지 있는거니까 승.(이것이 핵심)

만약 d(0,0,0)상태는? 상대가 먹고 온 상태라서 이긴 상태.
그럼 d(0,0,1)은 당연히 진 상태. => 초기값으로 사용.

교수님 코드보면 decision함수가 9가지 경우를 확인하는 코드이다.
여기서 한번이라도 컴퓨터가 패하면 자신은 승으로 리턴한다.

교수님 코드

2-2) 규칙 => 사실 난 이방법으로 풀었다.

0 0 0 0 0 0
0 0 0 0 0 0
0 1 2 3 4 5
W L W W W L?

이런식으로 관측이 되는데, 4 간격마다 진다(이겼던가?) 따라서 모든 숫자를 1,2,3,4 의 범위 내로 표현 가능하다.(나누던지 해서 나타내면 됨)
=> 이 범위 안에서 패배나 승리할 조건들은 금방 구할 수 있으니, 이들을 각각 조건문으로 처리한다.

여기서 Tip은 정렬을 통해서 d(7,8,6)이나 d(6,7,8)같은 케이스는 하나의 케이스로 보고 작성한다. 이렇게 하면 조건도 4개? 5개 정도만 하면 바로 풀린다.

교수님 코드