사용자 도구

사이트 도구


ps:problems:boj:9660

돌 게임 6

ps
링크acmicpc.net/…
출처BOJ
문제 번호9660
문제명돌 게임 6
레벨골드 5
분류

게임 이론

시간복잡도O(1)
사용한 언어Python 3.11
제출기록31256KB / 44ms
최고기록36ms
해결날짜2023/06/14

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
Q A K W S
 
ps/problems/boj/9660.txt · 마지막으로 수정됨: 2023/06/14 16:02 저자 teferi