테페리넷

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

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

===== 풀이 =====
  * [[ps:problems:boj:9656]]에서 한번에 4개의 돌을 가져갈 수 있는 방법이 추가되었다.
  * 이 규칙이 추가된 것만으로, 간단한 논리로 승리포지션의 규칙성을 찾는 것이 꽤 까다로워졌다. N의 범위가 작으므로 규칙성을 찾지 못해도, DP를 이용해서 승리 포지션을 계산할수 있다
    * 논리적으로 도출해내기는 조금 까다로울 뿐, 단순한 규칙이 존재하기는 한다. [[ps:problems:boj:9660]]은 이 문제에서 N의 범위를 늘려서 반드시 규칙성을 이용해야만 풀리도록 만든 문제이다.
  * 각 포지션에서 이동 가능한 포지션은 O(1)개이고, N개의 포지션에 대해서 계산해야 하므로, 총 O(N)에 계산 가능하다.

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

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

Tags: [Game theory]
"""


def main():
    N = int(input())

    is_win_pos = [False] * (N + 5)
    for i in range(N + 1):
        if not is_win_pos[i]:
            is_win_pos[i + 1] = is_win_pos[i + 3] = is_win_pos[i + 4] = True

    print('SK' if is_win_pos[N] else 'CY')


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

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