[백준 9658번] 돌 게임 4 (C++)

문제링크 : https://www.acmicpc.net/problem/9658

9658번: 돌 게임 4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int dp[1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;
    dp[1]=0; dp[2]=1; dp[3]=0; dp[4]=1; //1이 상근이가 이기는 경우
    for(int i=5; i<=N; i++)
    {
        if(dp[i-1] && dp[i-3] && dp[i-4]) dp[i]=0; 
        else dp[i]=1;
    }
    cout << (dp[N]==1 ? "SK" : "CY");
    return 0;
}

 

간단한 dp 문제인 돌게임이다.

처음 주어진 4개의 값에 대해서 초기화를 하고 진행한다.

상근이가 먼저 시작하고, 상근이가 이기는 것을 dp의 값이 1일 때를 기준으로 하였다.

 

돌은 1개,  3개 또는 4개 가져갈 수 있으므로 이에 따라 dp[1]=0, dp[2]=1, dp[3]=0,. dp[4]=1로 초기화해주었다.

dp[1] -> 1개 밖에 없으므로 짐

dp[2] -> 1개 가져가면 상대방이 나머지 가져가야 하므로 이김

dp[3] -> 1개를 가져가도 마지막에 다시 1개를 가져가야하고, 아니면 3개를 가져가야하므로 짐

dp[4] -> 3개를 가져가면 상대방이 마지막 1개를 가져가야하므로 이김

 

반복문은 i=5부터 N까지 돌려주고 직전 값이 (dp[i-1] && dp[i-3] && dp[i-4]) 1이라면 현재 dp는 0으로 아니라면 1 한다.

직전 값에 대한 모든 경우의 수가 1이라면 다음 대상은 0일수 밖에 없다.

이에 따라 dp[N]이 1이면 상근이가 이기고 아니라면 창영이기 승리한다.