백준 9655번 - 돌 게임 파이썬

📌 백준 9655번 - 돌 게임 (게임 이론 / DP)

✨ 문제 요약

1 또는 3개의 돌을 가져갈 수 있는 게임이 있다.
총 N개의 돌이 있으며, SK와 CY가 번갈아가며 돌을 가져간다.
마지막 돌을 가져가는 사람이 이긴다.

• SK가 항상 먼저 시작
• 이기는 사람의 이름을 출력 ("SK" 또는 "CY")

---

🧠 문제 해석

이 문제는 기초적인 게임 이론 또는 DP로 푸는 대표 문제다.
핵심은 "현재 돌 개수에 따라 이기는 사람이 정해진다"는 점이다.

---

✅ 수학적 풀이 (패턴 관찰)

N (돌 개수)	승자
1	SK
2	CY
3	SK
4	CY
5	SK

→ 홀수면 SK가 이기고, 짝수면 CY가 이긴다!

✨ 정답 코드 (수학 풀이)

N = int(input())
print("SK" if N % 2 == 1 else "CY")

---

✅ DP 풀이

🔧 상태 정의

dp[i] = True → 돌이 i개 남았을 때, 그 차례인 사람이 이길 수 있는 상태

🔁 점화식

dp[i] = not dp[i-1] or not dp[i-3]

→ 지금 차례인 사람이 1개 또는 3개를 가져가서
→ 상대방이 지는 상태로 만들 수 있다면 이긴다!

---

✅ 정답 코드 (DP 방식)

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

# 초기 상태
dp[1] = True   # SK 승
dp[2] = False  # CY 승
dp[3] = True   # SK 승

for i in range(4, N + 1):
    dp[i] = not dp[i - 1] or not dp[i - 3]

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

---

🧱 DP 테이블 예시

i (돌 개수) dp[i] 결과

1	True	SK 승
2	False	CY 승
3	True	SK 승
4	False	CY 승
5	True	SK 승

→ 홀수면 SK 승, 짝수면 CY 승 (수학 풀이와 일치!)

---

🧩 배운 점

• 게임 이론은 이긴 상태와 진 상태를 구분해서
  상대를 진 상태로 몰아넣을 수 있으면 내가 이긴다
• 이 문제는 수학적으로도 풀 수 있고,
  DP를 직접 구현하면서 승리 조건을 역추적해볼 수 있다

---

🎓 정리

항목 설명

문제 유형	게임 이론 / DP
수학 풀이	홀수 → SK, 짝수 → CY
DP 풀이	dp[i] = not dp[i-1] or not dp[i-3]
핵심 로직	이길 수 있는 상태를 만들어주는 선택이 있으면 True

---

🏷 해시태그

#DP #게임이론 #백준9655
#돌게임 #SKvsCY #파이썬DP
#백준Python #알고리즘공부