[9661] 돌 게임 7 - python 풀이

알고리즘 설계 기법

• Dynamic Programming
• 중복 호출을 해결하기 위해 수학적 접근 방법 사용

처음에 주어지는 돌 개수	필승 방법	이기는 사람
1	1	SK
2	1-1	CY
3	1-1-1	SK
4	4	SK
5	1-4 / 4-1	CY
6	4-1-1 / 1-4-1 / 1-1-4	SK
7	4-1-1-1 / 1-4-1-1 / 1-1-4-1 / 1-1-1-4	CY
8	7일때 후공이 반드시 이겼으므로, SK가 처음에 1개를 가져가서 필승	SK
9	5일때 후공이 반드시 이겼으므로, SK가 처음에 4개를 가져가서 필승	SK
10	9를 만들면 CY에게 주도권이 넘어가고, 6을 만들면 선공이 반드시 이겼으므로 CY필승 -> 즉 내가 10을 마주하는 순간 필패	CY
11	10이면 후공필승, 7이면 선공필승이므로 SK가 처음에 1개를 가져가서 자신을 후공 포지션으로 만듦 -> 필승	SK
12	11이든 8이든 그 상황을 마주한 플레이어가 게임을 주도할 수 있음 -> 즉 여기서 뭘 선택하든 진다 -> 내가 12를 만들면 상대는 무조건 진다	CY
13	12를 만들어서 필승	SK
14	내가 10을 만들어주면 상대는 필패	SK
15	14를 만드나 11을 만드나 상대방이 주도권을 쥐게 됨 -> 따라서 선공이었던 SK는 필패	CY
16	16	SK

사실 돌 개수 6개부터 필패와 필승은 계산해보지 않아도 알 수 있었다.

선공이 1개를 가져가서 5가 될 경우 -> 상대가 무엇을 선택하건 그 상황에서는 후공이 이김

선공이 4개를 가져가서 2가 될 경우 -> 상대가 무엇을 선택하건 그 상황에서는 후공이 이김

 

즉, 상황을 따지며 풀다보면 이기는 사람이 반복되는 것을 볼 수 있다.

따라서 돌 개수를 5로 나눠서 나머지가 2 또는 0이면 무조건 CY가 이기고, 아니면 무조건 SK가 이긴다.

 

답

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

문제 풀러가기

9661번: 돌 게임 7