테페리넷

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

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

===== 풀이 =====
  * [[ps:problems:boj:9657]]에서 승리조건과 패배조건만 뒤바뀐 문제.
  * [[ps:problems:boj:9657]]과 마찬가지로 N의 범위가 작으므로 DP를 통해서 O(N)에 풀수 있다. dp테이블에서 N=0일때의 값만 바꿔주고 dp를 돌리면 된다.

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

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

Tags: [Game theory]
"""


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

    is_win_pos = [False] * (N + 5)
    is_win_pos[0] = True
    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:실버_2}}