[백준 9657] 돌 게임 3

문제 : 돌 게임 3

문제 유형 : 다이나믹 프로그래밍

이 문제는 숭실대 알고리즘 대회에서 비슷한 문제가 나왔던 문제랑 거의 똑같다. (그 문제에는 승리, 패배만 있는게 아니라 무승부까지 있다.) 하지만 문제 푸는건 거기서 거기다.

두명이 다 최선을 다하여 게임을 한다는 가정과 돌을 1개, 3개, 4개 중 하나를 가지고 갈 수 있다는 조건이 있으므로 이 조건에 맞게 한번 DP 테이블을 채워보자.

가로에 써져 있는 건 현재 돌이 몇개 남았는지 뜻하는것이고 세로줄에는 SK이가 할 차례, CY가 할 차례를 표현한것이다. 

표를 채울때 1과 -1을 사용할 것이다. 1은 자신이 승리한다는 뜻이고 -1은 자신이 패배한다는 뜻으로 사용할 껏이다. (1과 0으로 해도 상관없다.)

돌이 1개, 3개, 4개가 남았을땐 누가 시작하든 먼저 시작한 사람이 이기니깐 다 1로 채운다.

돌이 2개 남을때를 채워보자. SK가 시작을 한다면 돌을 1개를 가지고 가야한다. SK가 돌 1개를 가지고 가면 돌이 1개가 남은 상태로 CY가 돌을 가져가야할 차례이다. 그러면 CY이가 시작하고 돌이 1개일때 표를 보자. 1이 있는데 이 뜻은 이대로 게임을 진행하면 CY가 이긴다는 뜻이다. 그러면 SK가 먼저 시작하고 2개인 칸에 -1을 채우자. 마찬가지로 2개가 남고 CY가 먼저 시작한다고 하면 SK가 이기므로 -1을 채우면 된다.

이젠 돌이 5개가 있을때를 보자. 돌이 5개 남았을 때, SK가 먼저 시작한다고 보자. 돌이 5개 있으니깐 SK는 돌을 1개, 3개, 4개를 가지고 갈 수 있다. 그러면 돌을 1개, 3개, 4개 가지고 갔을 때를 보자.

1개를 가지고 간다면 CY가 승리하고, 3개를 가지고 간다면 CY가 패배(즉 SK가 승리)하고, 4개를 가지고 가면 CY가 승리한다는 것을 알 수 있다. SK와 CY는 최선을 다해 게임을 하니깐 SK는 돌을 3개 가지고 가서 승리를 할 것이다. 따라서 표에 1을 채우면 된다. 마찬가지로 돌이 5개 남고 CY가 시작한다고 하면 CY가 승리하므로 1을 채우면 된다.

이러한 규칙으로 바로 코딩을 해도 된다. 하지만 난 이 규칙을 찾기 전(숭실대 대회때)엔 어느정도 DP 테이블을 채우고 규칙을 찾았었다. 아래는 8까지 채워나가는 과정이다.

한번 정리를 하자면 현재 상태에서 자기가 가지고 갈 수 있는 만큼 다 가지고 가본다. 가지고 갔을 때 그 다음 상황에서 자신이 승리할 수 있는 방법이 하나 이상 존재한다면 그 게임은 승리하고 만약에 이길 수 있는 방법이 없다하면 그 게임은 무조건 진다. 이를 소스코드를 짜면 아래와 같다.

#include<iostream>
#include<algorithm>
 
using namespace std;
typedef long long ll;
 
ll dp[2][2000];
ll rock[3] = { 1,3,4 };
 
void solve(int n)
{
    dp[0][1] = dp[0][3] = dp[0][4] = 1;
    dp[1][1] = dp[1][3] = dp[1][4] = 1;
    for (int i = 2; i <= n; i++)
    {
        if(dp[0][i])continue;
        for (int j = 0; j < 2; j++)
        {
            int check = 0;
            for (int k = 0; k < 3; k++)
            {
                int idx = i - rock[k];
                if (idx < 0)continue;
                if (dp[1 - j][idx] == -1)
                {
                    check = 1;
                    break;
                }
                check = -1;
            }
            dp[j][i] = check;
        }
    }
    if (dp[0][n] == 1)
    {
        cout << "SK";
    }
    else
    {
        cout << "CY";
    }
}
 
int main()
{
    int n;
    cin >> n;
    solve(n);
    return 0;
}