[파이썬, Python] 백준 9655: 돌 게임

문제

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

9655번: 돌 게임

코드

n = int(input())
if n % 2 == 0:
    print("CY")
else:
    print("SK")

n = int(input())

dp = [''] * 1001

dp[1] = "SK"
dp[2] = "CY"
dp[3] = "SK"

for i in range(4, n+1):
    if dp[i-1] == "SK":
        dp[i] = "CY"
    
    else:
        dp[i] = "SK"

print(dp[n])

설명

[풀이 1]
간단하게 생각하면 쉽게 풀리는 문제이다.

n이 홀수라면 상근이가,
n이 짝수라면 창영이가 게임을 이기게 된다.

숫자를 1개에서 3개만 부를 수 있으므로,
만약 내가 5를 외쳐야 한다면 그전 단계에선 1을 외쳐야 승리를 하게 된다.(상대가 3개를 불러도 2,3,4 이므로)

따라서 n을 4로 나눈 나머지가 1이거나 3이라면(2는 부를 수 없으므로) 처음 시작한 사람이 이기고,
그렇지 않다면 나중에 시작한 사람이 이기게 된다.
4로 나눈 나머지가 1 혹은 3인 경우는 2로 나눈 나머지가 1인 경우와 같으므로 식을 바꿀 수 있다.

[풀이 2]
1번 풀이에 근거해서 나오는 DP 식이다.

n이 홀수인 경우에는 SK를,
n이 짝수인 경우에는 CY를 출력할 수 있다.