9655: 돌 게임

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

9655번: 돌 게임

설명

핵심 아이디어

• 다이나믹 프로그래밍
• 작은 문제부터 시작하자!
• 돌의 개수가 홀수 일 때는 SK이고 돌의 개수가 짝수 일 때는 CY를 출력하면 된다.

코드 구현

# 1 

처음에는 풀었을 때 답은 맞았으나 시간이 오래 걸려서 갸우뚱 했었다. DP로 푸는게 맞나 싶은 생각이 들었다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [""] * (n+1)

for i in range(1, n+1):
	if i % 2 == 0:
		dp[i] = "CY"
	else:
		dp[i] = "SK"
print(dp[n])

# 2

해당 코드는 다른 사람의 풀이를 참조해서 풀었는데, 더 DP 스럽게 풀어서 해당 코드로 연습해야겠다. 그런데 이 방식도 시간이 오래 걸려서 DP를 사용하지 않고도 풀 수 있는거 같다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [-1] * 1001

dp[1] = 1 # SK
dp[2] = 0 # CY
dp[3] = 1 # SK
for i in range(4, n+1):
	if dp[i-1] == 1 or dp[i-3] == 1:
		dp[i] = 1
	else:
		dp[i] = 0
if dp[n] == 1:
	print("SK")
else:
	print("CY")

# 3 dp를 사용하지 않고 단순하게 풀 수 있었다.

import sys
input = sys.stdin.readline

n = int(input())

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