[백준/파이썬] 9657: 돌 게임3

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

9657번: 돌 게임 3

문제 요약 : 돌 N개가 있다. 상근과 창영은 턴을 번갈아가며 돌을 1,3,4개 중 골라 가져갈 수 있다. 마지막으로 돌을 가져가는 사람이 이긴다.

 

예제 입력 1 :

6

예제 출력 1 :

SK

 

 

📌 풀이 )

문제의 규칙을 알아내기 위하여 일단 쭉 작성해보았다.

 

상근이가 이기면 1, 창영이가 이기면 0을 작성하였다.

dp[1] = 1
dp[2] = 0
dp[3] = 1
dp[4] = 1
dp[5] = 1
dp[6] = 1
dp[7] = 0
dp[8] = 1
dp[9] = 0
dp[10] = 1

dp[1],dp[3],dp[4]는 상근이가 1개, 3개, 4개를 가져가서 이기는 게임이다.

dp[2]는 상근이가 1개밖에 가져가지 못하고, 그로 인해 창영이가 이기는 게임이다.

 

상근이가 이기는 경우를 생각해보자.

dp[n]을 n번째 돌을 가져가는 사람의 이름이라고 생각해보자.

5번째 돌이 가져가는 첫번째 돌일 경우, 그 전에 가져간 사람은 dp[4]에서 끝나게 된다. dp[4]는 상근이가 가져갔다.그렇다면 dp[5]는 창영이가 가져가게 된다.

5번째 돌이 가져가는 세번째 돌일 경우, 그 전에 가져간 사람은 dp[2]에서 끝나게 된다. dp[2]는 창영이가 가져갔다. 그렇다면 dp[5]는 상근이가 가져가게 된다.(여기서 상근이가 돌을 하나가져가면, 창영이가 4개를 가져가지 왜 2개를 가져가겠냐는 식으로 생각해선 안된다. 이해를 돕기위하여 순서를 바꾼 것이고, 상근이가 3개를 먼저가져가고, 창영이가 1개, 상근이가 1개를 가져갈 수 있기 때문이다.)

5번째 돌이 가져가는 네번째 돌일 경우, 그 전에 가져간 사람은 dp[1]에서 끝나게 된다. dp[1]은 상근이가 가져갔다. 그렇다면 dp[5]는 창영이가 가져가게 된다.

 

그런데 이 게임은 언제나 상근이가 먼저 시작한다. 그렇다면 상근이는 2번째 사례대로 자신이 이기게 조정할 것이다. 그러면 dp[5]는 1이 된다.

 

그렇다면, 창영이가 이기는 경우를 생각해보자.

7번째 돌이 가져가는 첫번째 돌일 경우, dp[6]은 상근이였기 때문에 창영이가 가져가게 된다.

7번째 돌이 가져가는 세번째 돌일 경우, dp[4]는 상근이였기 때문에 창영이가 가져가게 된다.

7번째 돌이 가져가는 네번째 돌일 경우, dp[3]은 상근이였기 때문에 창영이가 가져가게 된다.

즉, 7번째 돌이 무슨 경우에서든 창영이가 가져가게 된다.

 

즉 dp[i-1], dp[i-3], dp[i-4] 모두가 상근이가 나와야만 창영이가 이길 수 있다.

# 돌 게임 3
N = int(input())
dp = [1,1,0,1,1]
for i in range(5,N+1):   
        if dp[i-1] + dp[i-3] + dp[i-4] == 3 :
            dp.append(0)
        else :
            dp.append(1)

if dp[N] == 1 :
    print("SK")
else :
    print("CY")

참고로, 그냥 7로 나누어서 나머지가 0과 2인 경우만 창영이가 이기는 규칙을 찾아내는 방법도 있다!