백준 9655 c++ "돌 게임" -PlusUltraCode-

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

 

[필자 사고]

홀 수 짝수 개념으로 해도 문제는 풀린다.

다만 DP공부중이기 때문에 dp적 사고로 풀어야 겠다.

문제에서 주어진 조건은 1과 3 

즉 점화식을 구해보면 현재 DP = 과거(DP1) 과 과거(DP3) +1 을 해서 flag 형태로 풀게되면 문제는 풀린다.

[코드 해설]

1. 문제 개요

이 문제는 돌을 1개 또는 3개 가져갈 수 있는 돌 게임에서 마지막 돌을 가져가는 사람이 승리하는 게임입니다.

• 상근(SK)과 창영(CY)이 번갈아 가며 돌을 가져갑니다.
• N개의 돌이 있을 때, 누가 이기는지를 출력하는 문제입니다.

---

2. 입력 처리 및 초기 조건

1. N을 입력받습니다.
2. dp 배열을 선언하여, dp[i]는 i개의 돌이 있을 때 최소 턴 수를 저장합니다.
3. 초기 값:
   • dp[0] = 0 (게임 시작 전)
   • dp[1] = 1 (1개 남으면 바로 가져감 → 1턴)
   • dp[2] = 2 (1개 + 1개로 가져가야 함 → 2턴)

---

3. DP 점화식 및 계산

• dp[i] = min(dp[i - 1] + 1, dp[i - 3] + 1);
  • 돌을 가져갈 수 있는 방법:
    1. dp[i - 1] + 1: 1개 가져간 경우 (i-1까지의 최소 턴 + 1)
    2. dp[i - 3] + 1: 3개 가져간 경우 (i-3까지의 최소 턴 + 1)
  • 두 경우 중 더 작은 턴 수를 선택하여 dp[i]를 갱신합니다.

---

4. 승자 판별

• dp[N]이 홀수이면 SK 승리
• dp[N]이 짝수이면 CY 승리

[소스 코드]

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N;
	int dp[1000];

	cin >> N;
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;

	for (int i = 3; i <= N; i++) {
		dp[i] = min(dp[i - 1] + 1, dp[i - 3] + 1);
	}

	if (dp[N] % 2 == 1)cout << "SK";
	else cout << "CY";
}