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()
ps/problems/boj/9657.txt · 마지막으로 수정됨: 2023/06/14 05:01 저자 teferi
토론