[백준] 9655번

💻 C++ 기반

돌 게임
https://www.acmicpc.net/problem/9655

1. 테이블 정의하기
dp[i]: i번째 돌을 가져가는 사람 (1이면 상근, 2이면 창영)

2. 점화식 찾기
k개의 돌이 남아있을 때, 누군가가 1개의 돌을 가져가면 그 다음 턴 사람은 k-1개 중에서 선택해야 한다 -> dp[k-1]은 dp[k]와 반대 값
k개의 돌이 남아있을 때, 누군가가 3개의 돌을 가져가면 그 다음 턴 사람은 k-3개 중에서 선택해야 한다 -> dp[k-3]은 dp[k]와 반대 값

3. 초기값 정하기
게임은 상근이가 시작하므로 N번째 돌은 무조건 상근이가 가져간다.
dp[N] = 1

#include <cstdio>

#define MAX 1001

using namespace std;

int dp[MAX];

int main()
{
    int N;
    scanf("%d", &N);

    dp[N] = 1;
    for (int i = N; i > 1; i--)
    {
        if (i - 1 >= 0)
        {
            dp[i - 1] = dp[i] == 1 ? 2 : 1;
        }
        if (i - 3 >= 0)
        {
            dp[i - 3] = dp[i] == 1 ? 2 : 1;
        }
    }

    if (dp[1] == 1)
    {
        printf("SK");
    }
    else if (dp[1] == 2)
    {
        printf("CY");
    }
    return 0;
}