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