[백준] 9665번 - 돌게임

백준 9665 : 돌게임

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

예제 입력 1 

5

예제 출력 1 

SK

---

문제 요약

• 돌이 N개
• 한 턴에 1개 또는 3개만 가져갈 수 있음
• 마지막 돌을 가져간 사람이 승리
• 상근 이 먼저 시작

즉, 현재 상태에서 이길 수 있는지 없는지를 미리 계산해야 함

왜 DP를 선택했는가

이 문제는 현재 상태의 승패가 이전 상태의 승패에 의존하고, 같은 상태가 반복해서 필요해지기 때문에 결과를 저장하는 DP를 쓰는 것이 가장 효율적이라고 생각했다

DP 정의

dp[i] =True  → 돌이 i개일 때, 현재 턴의 사람이 이길 수 있다
dp[i] =False → 돌이 i개일 때, 현재 턴의 사람이 반드시 진다

코드 설명

1. 입력 및 DP 배열 생성

N =int(input())
dp = [False] * (N +1)

• dp[i]를 저장하기 위해 크기 N+1 배열 생성
• 처음엔 전부 False로 초기화

2. 기본 case

dp[1] =True# 돌 1개 → 1개 가져가서 바로 승리
dp[2] =False# 돌 2개 → 1개 가져가면 상대가 마지막 돌 → 패배
dp[3] =True# 돌 3개 → 3개 가져가서 바로 승리

직접 게임을 해보면 바로 알 수 있는 경우이다.

3. 점화식

for i inrange(4, N +1):
if dp[i -1] ==Falseor dp[i -3] ==False:
        dp[i] =True
else:
        dp[i] =False

현재 돌이 i개일 때

• 1개를 가져가서 상대가 지는 상태(i-1) 로 만들 수 있거나
• 3개를 가져가서 상대가 지는 상태(i-3) 로 만들 수 있으면 나는 이긴다

그래서 조건이 이렇게 됨

dp[i] =True  (이김)
↔ dp[i-1] ==False or dp[i-3] ==False

둘 다 True면?

상대가 항상 이기는 상태로만 넘겨짐 → 현재는 반드시 짐

4. 결과 출력

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

• dp[N]이 True → 선공인 상근(SK)이 이김
• dp[N]이 False → 창영(CY)이 이김

정리

이 풀이는 dp[i]를 돌이 i개 있을 때 현재 턴의 승패 상태로 정의하고,

1개 또는 3개를 가져간 뒤 상대가 패배 상태가 되는 경우가 하나라도 있으면

현재 상태를 승리로 판단하는 DP 풀이이다.

더 쉬운 풀이도 있다. 직접 N 이 1,2,3,4,..인 경우를 생각해보면 n이 짝수이면 창영이가 이기고 홀수이면 상근이가 이기는 게임이기 때문에 아래와 같이 간단한 풀이도 가능하다.

n = int(input())

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