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

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

9657번: 돌 게임 3

Problem

• 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

조건

• 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 
• 게임은 상근이가 먼저 시작한다.
• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

SOL

"두 사람이 완벽하게 게임을 한다"라는 문장을 신경안쓰고 풀어서, 엄청 헤매었던 문제.

완벽하게 게임을 한다는 의미는, 이길 수 있는 경우의 수가 있다면, 그 경우의 수만 놓는다는 의미.

바둑으로 따지면, 서로 최적의 수만 계속 놓는다는 의미이다.

 

항상 DP문제 중에, 이런 시뮬레이션 문제는 N=5까지는 해주는 편이다.

N=1	N=2	N=3	N=4	N=5
상근	창영	상근	상근	상근

서로 최선의 수만 놓는다고 했을 때, 상근이가 N=2개 일때 빼고는 이긴다.

여기까지 해봣을 때, 규칙성을 모르겠어서 N=6,7,8까지 해봤음.

N=6	N=7	N=8
상근	창영	상근

경우의 수를 구해주는 과정에서 알아낸게 있음!

• N번째 돌을 가져가면 이기는거니까, N-1,N-3,N-4번째에 상대턴이 1개라도 있으면, 이길 수 있다는걸 알게 됬다.

왜냐하면, 상대턴으로 넘길 수 있는 경우의 수가 있다면, 우리 똑똑한 상근이는 바로 그 경우의 수를 놓을 것이기 때문이다.(실제로는 이걸 못해서 지는거니까.. 알파고가 이긴 이유가 여기서!?)

#DP
N=int(input())
DP =[0]*1001

DP[1]=1
DP[3]=1
DP[4]=1
if N>=5:
    for i in range(5,N+1): 
        if not DP[i-1]:
            DP[i]=1
        if not DP[i-3]:
            DP[i]=1
        if not DP[i-4]:
            DP[i]=1

if DP[N]:
    print("SK")
else:
    print("CY")