9655 - 돌 게임

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

9655번: 돌 게임

생각해 보기

• 상근이와 창영이는 항상 최선의 수만을 둔다.
• 만약 1개를 놓던 3개를 놓던 자신이 이기는 경우가 있다면 그 수만 둘 것이다.
• 이미 해봤던 경우를 메모이제이션으로 지워주자.

코드

#include<iostream>

using namespace std;

int N;
int dp[1001][2];

int dfs(int cnt, int who){
    if(dp[cnt][who])
        return dp[cnt][who];

    int wflag = who?1:-1;
    int fflag = who?-1:1;

    if(cnt==N)
        return fflag;
    
    if(cnt+3<=N)
        dp[cnt+3][who] = dfs(cnt+3,who?0:1);
    dp[cnt+1][who] = dfs(cnt+1,who?0:1);

    return dp[cnt][who] = (dp[cnt+1][who]==wflag || dp[cnt+3][who]==wflag)?wflag:fflag;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N;
    if(dfs(0,1)==1)
        cout<<"SK"<<'\n';
    else
        cout<<"CY"<<'\n';

    return 0;
}