99클럽 코테 스터디 26일차 TIL: 게임

문제

https://www.acmicpc.net/problem/9655

풀이

알고리즘 분류중에 DP가 있다.
일단 DP적으로 생각하지 말고 최선의 선택을 했을 때, 누가 이기는지 패턴을 살펴보았다.

돌이 1개일 때, 바로 가저가면 되므로 상근이가 이긴다. SY
2 일때, 상근이는 1개 가져가는 행위 밖에 못한다. 그러므로 나머지 1개 가져가는 행위를 하면 됨(돌이 1개일 때) CY
3 일때, 상근이가 3개 가져가면 됨. SY

4 일때, 상근이가 1개를 가져가든 3개를 가져가든 창영이가 이김 CY
=> 여기서 상근이가 3개를 가져가는 행위를 통해 창영이는 돌이 1개일 때의 행위를 하면된다.
=> 상근이가 1개를 가져가면 창영이는 돌이 3개일 때 행위를 하면 됨

SY, CY가 반복된다. 홀수일 때는 SY 짝수일 때는 CY이다.

소스코드

후기

패턴만 발견하면 아주 쉽게 풀 수 있는 문제였다.