python 백준 9655 돌 게임

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

코드 설명

• check에는 최선의 수를 뒀을때 어느 쪽이 이기는지 기록
• check의 index는 돌이 index개 일때 이기는 쪽
• check[idx] 값이 True이면 "SK"가 이김
• 돌이 1개일때는 SK가 이김
• 돌이 2개일때는 SK가 1개를 가져가고, CY가 check[1]의 값이 True이므로 CY가 이기게됨
• 돌이 X개 일때는 SK가 1개 혹은 3개를 가져갈 수있음
• SK의 차례에서 (X-1)의 값이 False라면 1개를 가져가면 이길 수 있음(CY입장에선 X-1개의 돌이 주어지는데 X-1개의 돌이면 지는것을 check에 기록해뒀음)
• 마찬가지로 (X-3)의 값이 False라면 3개를 가져가면 이길 수 있음
• 이렇게 얻은 결과를 check[X]에 기록하고 해당 값을 X+1개의 돌에서 사용

def solution(N):
    check = [False]*(N+1)
    check[0] = True
    check[1] = True
    for i in range(2,N+1):
        if check[i-1] == False:
            check[i] = True
        elif i>=3 and check[i-3] == False:
            check[i] = True
    if check[N]:
        return "SK"
    return "CY"

N = int(input())
ans = solution(N)
print(ans)