백준 9655번: 돌 게임

[문제 링크]

---

간단한 DP 문제였다.

자신의 차례에서 1개나 3개를 가져갔을 때 상대방이 승리하는지 여부는 가져간 개수에서 상대방이 1개나 3개를 가져갔을 때 자신이 승리하는지 여부에 결정된다. 그리고 이것을 계속 반복하다가 결국 기저사례 (N=1, N=2, N=3)에 도달하게 되면 최종적으로 승리와 패배가 결정되게 된다. 점화식은 다음과 같다.

Dp(N) = !(DP(N-1) || DP(N-3))

 

참고로 이 문제는 베스킨라빈스31 게임처럼 규칙 상 무조건 승리하는 필승법이 있다. 짝수개가 남도록 가져가면 결국 상대방이 패배한다. 즉 N이 홀수면 상근이가 이기고, 짝수면 창영이 이기게 된다.

 

---

#include <iostream>
using namespace std;

bool memo[1001] = {false,};
bool visited[1001] = {false,};

bool Topdown(int remain)
{
    if(remain == 1 || remain == 3)
    {
        return true;
    }   
    else if(remain == 2)
    {
        return false;
    }
    
    if(visited[remain]) 
    {
        return memo[remain];        
    }
    
    visited[remain] = true;
    
    return memo[remain] = !(Topdown(remain-1) || Topdown(remain-3));
}

bool Bottomup(int remain)
{
    memo[1] = true;
    memo[2] = false;
    memo[3] = true;
    
    for(int i = 4; i<=remain; ++i)
    {
        memo[i] = !(memo[i-1] || memo[i-3]);
    }
    
    return memo[remain];
}

int main(void)
{
    int N;
    cin >> N;
    
    if(Topdown(N))
    {
        cout << "SK";
    }   
    else 
    {
        cout << "CY";
    }
    
    return 0;
}