[백준/Python] 9655 - 돌 게임

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

구현 과정

dp를 이용하는 문제인줄 알았는데, 막상 규칙을 찾으니까 굳이 dp로 풀 필요가 없었다!

[게임 규칙]
1. 게임은 SK가 먼저 시작한다.
2. 자리 차례에 돌을 1개 또는 3개 가져갈 수 있다.
3. 마지막 돌을 가져가는 사람이 이긴다.

• 돌의 개수 1개 - SK
• 돌의 개수 2개 - CY
• 돌의 개수 3개 - SK

여기서부터는 가능한 케이스를 모두 구해봐야 한다.

• 돌의 개수 4개 - (1 1 1 1), (1 3), (3 1) 모두 짝수 번 횟수로 끝나므로, CY가 이긴다. (여기서 슬슬 규칙이 나타날 기미가 보인다!)

• 돌의 개수 5개 - (1 1 3), (3 1 1), (1 3 1), (1 1 1 1 1) 모두 홀수 번 횟수로 끝나므로, SK가 이긴다.

• 돌의 개수 6개 - (1 1 1 1 1 1), (3 3), (1 1 1 3), (1 3 1 1), (1 1 3 1), (3 1 1 1) 모두 짝수 번 횟수로 끝나므로, CY가 이긴다.

종합해보면, 돌의 개수가 홀수인 경우 SK가 이기고, 짝수인 경우에는 CY가 이긴다. n을 입력받은 후 그냥 조건문으로 짝수/홀수인 경우를 구분해서 처리해주면 된다.

전체 코드

n = int(input())

if n % 2 == 0:
    print("CY")
else:
    print("SK")