ps:problems:boj:9656
돌 게임 2
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 9656 |
| 문제명 | 돌 게임 2 |
| 레벨 | 실버 4 |
| 분류 |
게임 이론 |
| 시간복잡도 | O(1) |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 31256KB / 44ms |
| 최고기록 | 36ms |
| 해결날짜 | 2023/06/12 |
풀이
- 돌 게임에서 승리조건이 반대로 된 경우이다. 비슷한 방법으로 규칙성을 찾을수 있다.
- 내 차례가 왔을때 돌의 갯수가 1개이면 패배한다. 따라서 내 차례가 왔을때 돌이 2개나 4개라면, 1개만 남기고 상대방한테 넘겨줄수 있으므로 이길 수 있다.
- 돌 게임와 마찬가지로 내 차례에서 돌을 x개로 만들수 있다면, 다음 내차례에는 다시 돌을 x-4개로 만들수 있는 방법이 존재한다. 내 차례에서 돌을 4k+1개로 만들수 있다면 승리할수 있고, 이 말은 내 차례가 왔을때 돌이 4k+2 또는 4k+4개, 즉 짝수개라면 항상 이길 수 있다는 말과 같다
코드
"""Solution code for "BOJ 9656. 돌 게임 2".
- Problem link: https://www.acmicpc.net/problem/9656
- Solution link: http://www.teferi.net/ps/problems/boj/9656
"""
def main():
N = int(input())
print('SK' if N % 2 == 0 else 'CY')
if __name__ == '__main__':
main()ps/problems/boj/9656.txt · 마지막으로 수정됨: 2023/06/12 07:04 저자 teferi
토론