백준 9656번- '돌 게임 2' (PYTHON 풀이)

문제:

 

N을 입력받고 두 명의 플레이어가 최적의 플레이를 했을 경우, 누가 이기는가에 대한 문제이다.

각 플레이어들은 돌을 1개 또는 3개씩만 뺄 수 있다고 한다.

 

풀이:

N = int(input())

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

필자는 처음 문제를 보자마자, 설마 하면서 위 코드를 작성하였다.

그림이나 알고리즘을 파악하기도 전에, 2로 나눴을 때 나눠떨어지면 SK, 아니면 CY 아닌가? 생각했는데 그게 정답이었다.

 

왜 이렇게 풀면 풀리는지 좀 더 자세히 살펴보겠다.

N	설명	승자
1	1개 집으면 바로 패배	CY
2	1개 → 상대 1개(패배)	SK
3	1 or 3 → 바로 패배	CY
4	1 → 3(CY), 3 → 1(CY)	SK
5	1 → 3→ 1(SK), 3 → 1 → 1(SK)	CY
6	1 → 3 → 1 → 1(CY), 3 → 3(CY)	SK

6개 정도 직접 작성해봤는데, 이를 통해 N이 짝수일 때는 SK가 승자이고 홀수일 때는 CY가 승자인 것을 확인할 수 있다.

모든 경우의 수를 작성하진 않았지만 직접 생각해보면 어떻게 이렇게 되는지 알 수 있을 것이다. 설명보다 중요한 것은 N이 어떨 때 승자가 누구인지를 파악하는 것인데, 결론적으로 N이 짝수일 때는 SK가 승자이고 홀수일 때는 CY가 승자인 것을 활용해서 코드를 작성하면 위와 같다. 2로 나누었을 때 나머지가 0이면 2로 떨어진다는 의미이므로 SK가 승자이고, 그것이 아니라면 CY가 승자이니 이를 그대로 출력만 해주면 된다.