9655 돌 게임

9655. 돌 게임 / c++ / Silver5 / 16분

문제

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

1. 상근이와 창영이가 N개의 돌을 번갈아가며 가져간다.
2. 한번 가져갈 때 1개 또는 3개만 가져갈 수 있다.
3. 상근이가 선공이고, 둘 다 완벽하게 게임한다고 할 때, 승자를 출력하라.

접근 방식

동적 프로그래밍

1. 경우의 수는 1개를 가져갈지, 3개를 가져갈지
2. 그리고 선공인지, 후공인지 이다.
3. 즉 DP(N, K)라고 할 때 (N은 현재 남은 돌의 갯수, K는 0이면 선공 1이면 후공)
4. dp[N-1][(K+1)%2] 가 1(승리) 이거나, dp[N-3][(K+1)%2] 가 1이면 dp[N][K] = 1이 된다. (선후공이 바뀐 상태의 N-1, N-3의 돌 중 하나라도 승리면 N, K도 승리)

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;

int N;
int dp[1'001][2] = {};

int DP(int n, int k)
{
    if (dp[n][k] == 0)
    {
        int nextK = (k + 1) % 2;
        if (DP(n - 1, nextK) == 1 || DP(n - 3, nextK) == 1)
        {
            dp[n][k] = 1;
            dp[n][nextK] = -1;
        }
        else
        {
            dp[n][k] = -1;
            dp[n][nextK] = 1;
        }
    }

    return dp[n][k];
}

int main()
{
    cin >> N;

    dp[1][0] = 1;
    dp[1][1] = -1;
    dp[2][0] = -1;
    dp[2][1] = 1;
    dp[3][0] = 1;
    dp[3][1] = -1;

    if (DP(N, 0) == 1) cout << "SK\n";
    else            cout << "CY\n";

    return 0;
}

다시 생각해 볼 점

1. 시간효율이 더 좋은 코드를 봤더니 N % 2 == 0 이면 후공 승, 아니면 선공 승이였다
2. 그렇게 간략하게는 풀지 못했지만, DP에 맞게 생각하고 해결해서 만족.