사용자 도구

사이트 도구


ps:problems:boj:9657

돌 게임 3

ps
링크acmicpc.net/…
출처BOJ
문제 번호9657
문제명돌 게임 3
레벨실버 3
분류

게임 이론

시간복잡도O(n)
인풋사이즈n<=1000
사용한 언어Python 3.11
제출기록31256KB / 44ms
최고기록36ms
해결날짜2023/06/14

풀이

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

코드

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

토론

댓글을 입력하세요:
J R T I T
 
ps/problems/boj/9657.txt · 마지막으로 수정됨: 2023/06/14 05:01 저자 teferi