백준 문제 9657번 돌 게임 3 문제풀이 c++

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

9657번: 돌 게임 3

문제해석

 

이 문제는 dp로 해결 가능하다.

dp[n]이 0일때 상근 승리 , 1일때 창영 승리라고 정의하면 첫턴은 무조건 상근이이므로

dp[n-1],dp[n-3],dp[n-4]를 보아서 그 셋이 전부 0이라면(dp[n-1],dp[n-3],dp[n-4]셋이 전부 상근 승리)

dp[n]은 상근이가 1개를 가져가든 3개를 가져가든 4개를 가져가든 다음턴에는 무조건 창영이가 승리한다.

그 반대로 그 셋이 전부 1이라면 상근이가 1개를 가져가든 3개를 가져가든 4개를 가져가든 다음턴에는 무조건 상근이가 승리한다.

그러나 셋중 하나라도 창영이 승리하는 경우가 있다면 주도권이 상근이에게 있으므로 무조건 상근이가 승리한다.

이게 설명으로 이해가 가지 않는다면 N=1부터 차근차근 써보면서 보면 쉽게 찾을 수 있다.

이 생각을 바탕으로 아래와 같이 코드를 작성했다.

 

코드

 

#include <iostream>
#include <algorithm>
using namespace std;
bool a[1001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    a[1]=0;
    a[2]=1;
    a[3]=0;
    a[4]=0;
    a[5]=0;
    for(int i=6; i<1001; i++)
    {
        if(a[i-1]==a[i-3]&&a[i-1]==a[i-4])
        {
            if(a[i-1]==0)
            {
                a[i]=1;
            }
            else
            {
                a[i]=0;
            }
        }
        else
        {
            a[i]=0;
        }
    }
    int n;
    cin>>n;
    if(a[n]==0)
    {
        cout<<"SK";
    }
    else
    {
        cout<<"CY";
    }
}