테페리넷

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

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

===== 풀이 =====
  * [[ps:problems:boj:9657]]에서 N의 범위만 키운 문제.
  * [[ps:problems:boj:9657]] 에서는 게임 규칙으로부터 승리 조건을 도출하는 것이 간단하지 않은 대신에, N의 범위가 작아서 DP를 이용해서 모든 결과를 다 구해보는 방식으로 해결했다. 하지만 이 문제에서는 N이 너무 커서 그러한 방법은 불가능하다.
  * 대신 DP를 통해서 작은 N에 대해서 결과들을 구해보고 나면, 쉽게 승리조건의 규칙성을 발견할 수 있다. N을 7로 나눈 나머지가 0 또는 2일 경우에만 후공이 승리하고, 나머지는 선공이 승리한다.
    * 이렇게 찾아낸 규칙성이 진짜로 맞는지는 귀납법을 이용해서 어렵지 않게 증명 가능하다. 
  * 규칙성을 이용하면 특정 N이 승리포지션인지 아닌지는 O(1)에 계산 가능하다


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

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

Tags: [game theory]
"""


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


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

{{tag>BOJ ps:problems:boj:골드_3 ps:teflib:linear_homogeneous_recurrence}}