[백준] 9657번 - 돌 게임 3 (Python)

문제

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

9657번: 돌 게임 3

 

접근 방법

기본적으로 N이 1, 3, 4면 선공이 이기고 2면 후공이 이긴다.

N이 5이상일 경우에는, 내가 선공을 했다고 했을 때

1) 1/3/4개를 가져가는 경우 중 하나라도 후공이 이기는 N값을 만들 수 있는 경우

→ 상대는 후공이 승리하는 N값인 상태에서 선공을 해야하므로 무조건 진다. 따라서 선공이 이긴다.

2) 1/3/4개 어느 경우를 가져가도 선공이 이기는 N값이 되는 경우

→ 상대는 선공이 승리하는 N값인 상태에서 선공을 하므로 무조건 이긴다. 따라서 후공이 이긴다.

 

코드

N = int(input())
maxN = 1000

isFirstWin = [False] * (maxN + 1) # isFirstWin[i]는 N=i일 때 선공이 이기는지 여부
isFirstWin[1] = True
isFirstWin[3] = True
isFirstWin[4] = True

for i in range(5, N + 1):
    # 몇 개를 가져가든 그 다음에 선공이 이기는 수를 넘겨줄 수 밖에 없다면 후공이 이기게 된다.
    if isFirstWin[i - 1] and isFirstWin[i - 3] and isFirstWin[i - 4]:
        isFirstWin[i] = False
    else:
        isFirstWin[i] = True
        
if isFirstWin[N]:
    print("SK")
else:
    print("CY")

 

풀이 정보

시도 횟수: 1회

총 문제 풀이에 걸린 시간: 15분 1초