테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 돌 게임 ======

===== 풀이 =====
  * N의 범위가 작으므로 DP를 통해서도 승리조건을 계산할수 있지만, 논리를 이용해서 규칙성을 파악하는 방식이 훨씬 간단하다
    * [[ps:problems:boj:9659]]은 똑같은 조건에서 DP를 통해 계산하는 것이 불가능하도록 N의 범위를 키운 버전이다
  * 배스킨라빈스 게임과 비슷한 방식으로 분석한다. 내 차례에서 돌의 갯수를 x개로 만들 수 있다면, 상대가 다음에 어떻게 하든 나는 다음 내차례에서 돌의 갯수를 다시 x-4개로 만들수 있다.
  * 돌의 갯수를 0개로 만들면 이기는 게임이므로, 내 차례가 왔을때 돌의 갯수가 1개 또는 3개라면 이길수 있다. 그리고 여기에 위의 논리를 추가하면, 내 차례가 왔을때 돌의 갯수가 4k+1 또는 4k+3개라면 이긴다. 바꿔 말하면, 내 차례가 왔을때 돌의 갯수가 홀수개라면 항상 이길수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9655. 돌 게임".

- Problem link: https://www.acmicpc.net/problem/9655
- Solution link: http://www.teferi.net/ps/problems/boj/9655
"""


def main():
    N = int(input())
    print('SK' if N % 2 else 'CY')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_5}}