[백준] 9655번 돌 게임

https://www.acmicpc.net/problem/9655

9655번: 돌 게임

 

풀이

두 사람이 돌을 1개 또는 3개씩 가져가면서 마지막 돌을 가져가는 사람이 이기는 게임이다.
두 사람이 1개 또는 3개의 돌을 가져갈 수 있는 경우는 1/1, 1/3, 3/1, 3/3 이고 서로 무조건 이기기 위한 선택을 하기 때문에
N번째에서 이긴 사람이 N+2, N+4, N+6에서도 모두 이기게 된다.

즉 홀수, 짝수로 나뉘어져 승리하는 인원이 정해진다.
DP 기본적인 문제를 다시 풀려고 선택하였지만 단순한 문제가 되어버렸다.

 

전체 코드

N = int(input())
if N % 2 == 0: print('CY')
else: print('SK')

1번째에 승리하는 사람이 3, 5, 7, ....
2번째에 승리하는 사람이 4, 6, 8, ... 으로 가기 때문에 홀짝으로 나눠서 문제를 풀면 된다.