사용자 도구

사이트 도구


ps:problems:boj:9658

돌 게임 4

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

게임 이론

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

풀이

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

코드

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

토론

댓글을 입력하세요:
D Q D W U
 
ps/problems/boj/9658.txt · 마지막으로 수정됨: 2023/06/14 05:04 저자 teferi