백준 문제 9661번 돌 게임 7 문제풀이 c++

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

9661번: 돌 게임 7

문제해석

이 문제도 앞선 돌게임 시리즈처럼 풀면되는데 이 문제에서는 가져가는 돌의 양이 바뀌었고 N역시 무지 크기 때문에 

dp로 푸는 것이 불가능하다.

어떻게 풀지 고민하다 일단은 n=1부터 누가 이기는지 찾다보면 패턴이 있을거라 생각했고

손으로풀다가 헷갈려서 그냥 dp를 사용해서 대략 n=200정도까지 출력해보았다.

 

패턴을 찾기 위해 dp로 작성한코드

#include <iostream>
#include <cmath>
typedef long long int ll;
using namespace std;
ll check(ll n);
int a[10001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    a[0]=1;
    a[1]=0;
    a[2]=1;
    a[3]=0;
    for(ll i=4; i<10001; i++)
    {
        for(ll j=check(i); j>=0; j--)
        {
            if(a[i-(int)pow(4,j)]==1)
            {
                a[i]=0;
                goto Label;
            }
        }
        a[i]=1;
Label:
        continue;
    }
    for(ll i=0; i<=200; i++)
    {
        if(a[i]==1)
        {
            cout<<i<<" CY\n";
        }
        else
        {
            cout<<i<<" SK\n";
        }

    }
}
ll check(ll n){
    ll i=0;
    while(1)
    {
        if(pow(4,i)<=n&&n<pow(4,i+1))
        {
            return i;
        }
        i++;
    }
}

의외로 dp로 작성하는것도 쉽진 않았다.

0은 볼 필요없고

1부터 200까지의 답이 아래 링크를 들어가면 나오는데

https://ideone.com/iyJ3OP

 

자세히 보면 5번마다 주기를 가지고 이걸 바탕으로 아래와 같이 작성하였다.

 

 

코드

#include <iostream>
typedef long long int ll;
using namespace std;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n;
    cin>>n;
    if(n==1||n==3)
    {
        cout<<"SK\n";
    }
    else if(n==2)
    {
        cout<<"CY\n";
    }
    else
    {
        if((n-3)%5==1||(n-3)%5==3||(n-3)%5==0)
        {
            cout<<"SK\n";
        }
        else
        {
            cout<<"CY\n";
        }
    }

}