백준 9657 돌 게임3

문제 URL : https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

문제 접근법 :

수학같은 문제인데

반드시 최적으로 게임했을때 n번째에 누가 이기는지 맞추는게임입니다.

돌을 1,3,4 개만 가져갈수있으니 반드시 조건에 맞게 가져가야합니다. 마지막에 돌을 가져간 사람이 이기니

상근이가 이길때를 1로 상근이가 질때를 0으로 표시한다면

 

돌이 1개일때 상근 이 이기므로 1입니다.

돌이 2개일땐 상근이가  집니다.  반드시 1개밖에 가져갈 수 밖에없고

창영이가 남은한개를 가져가는 경우밖에없으니  0이됩니다.

 

3개를 가져가서 2개를 가져가는 행동은 못합니다. 반드시 저개수에 맞게 가져가야합니다.

 

돌이 3개,4개일땐 그에 맞게 3개,4개를 다가져가면되니 1입니다.

그럼 5개일땐 1개를 가져간다면 4개일땐 지게되므로 1개를 가져가면안됩니다.

3개를 가져가서 돌을 2개로 만들면 창영이는 반드시 1개밖에 못가져가므로 3개를 가져가는것이 최선이니

상근이가 이깁니다. 1

 

그럼 6개일때도 마찬가지로 상근이가 첫번째에 4개를 가져가서 돌을 2개로만들면 창영이는 지게되니 상근이가 이길수밖에없어 1입니다.

마지막으로 7일땐 : 상근이가 1개를 가져가면 6개일땐 창영이가 이길수밖에없고 ,3개를 가져간다면 4개일때도 질수밖에없고 4개를 가져가도 3개가 남아도 질수밖에없으니 0입니다.

규칙이보이세요?

현재의 -1 번째 혹은 현재-3 혹은 현재 -4에서 0있는수가 있다면 반드시 1을 가질수있지만

없다면 반드시 지게됩니다.

즉 

check[n] = !check[n-1] or !check[n-3] or !check[n-4] 가 성립합니다.

 

이것을 파이썬으로 구현하게되면 !는 사용할수없으니 1 xor로 반전시켜야합니다.

 

소스코드:

import sys
input = sys.stdin.readline
n = int(input())
res=["CY","SK"]
check = [0,1,0,1,1]+[0]*(n)
for i in range(5,n+1):
    check[i]= check[i-1]^1 or check[i-3]^1 or check[i-4]^1
print(res[check[n]])

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.