[BOJ] Python 백준 돌게임(9655)

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

 

 

해당 문제는 2개의 풀이가 가능하다.

 

그리디 풀이 방식

import sys
input = sys.stdin.readline

N = int(input())

# 1개 혹은 3개
chk = -1
while N >0:
    chk = -chk
    if N - 3 >0:
        N -= 3
    else:
        N -= 1



if chk == 1:
    print("SK")
else:
    print("CY")

 

 

 

dp 풀이 방식

import sys
input = sys.stdin.readline

N = int(input())

dp = [False] * (N+1)
dp[1] = True

if N >= 2:
    dp[2] = False

if N >= 3:
    dp[3] = True

for i in range(4,N+1):
    if not dp[i-1] or not dp[i-3]: # 이전에 결과에서 한개 혹은 3개가 추가될 경우, 
    
        dp[i] = True # 승부 결과는 반대로 이루어지기에 만약 위 조건처럼 이전에 상대가 이긴 경우, 그 상태에서 1개 혹은 3개가 추가되면 반대편 상대가 이기게 된다.
    else:
        dp[i] = False

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

 

 

회고.

첨에 dp 느낌이라고 생각도 못하고, 바로 그리디로 접근해서 풀었다. 만약 수가 기하급수적으로 커지거나 예외적인 상황이 있을 경우 그리디는 위험도가 높다 그래서 dp로도 접근하는 방법을 꾸준히 생각해야겠담...