BOJ 30408 - 춘배가 선물하는 특별한 하트

제1회 춘배컵에 나온 문제다. 

춘배는 귀엽다!! 나비도 귀엽다!!

 

---

체감 티어 : G5

태그 : map, dp, recursion

 

문제가 정말 친절하다. 

A가 짝수면 /2, 홀수면 (A-1)/2, (A-1)/2+1로 분할해서 M을 만들 수 있는지 확인하는 문제이다.

간단한 재귀함수로 구현하면 ...

int f(ll n, ll m){
    if(n==m){
        return 1;
    }
    if(n<m){
        return 0;
    }
    if(~n&1)return f(n/2,m);
    else{
        return max(f((n-1)/2,m),f((n-1)/2+1,m));
    }
}
int main(){
    fastio;
    ll n, m;
    cin>>n>>m;
    cout<<(f(n,m)?"YES":"NO");
    return 0;
}

시간초과가 난다.

시간초과를 해결하기 위해선 dp를 사용하면 될거 같은데.. 문제는 N제한이 10¹⁸이기 때문에 dp를 하기는 어려워보인다..

그렇다면 재귀를 하면서 나오는 수들을 hash_map을 이용해 저장해서 이미 저장된 수인지 판별하는 방법은 어떨까?

충분히 가능하다. 이를 구현하면 문제를 해결할 수 있다.

 

map<ll, int>mp;
int f(ll n, ll m){
    if(mp.find(n)!=mp.end())return mp[n];
    if(n==m)return mp[n]=1;
    if(n<m)return 0;
    if(~n&1)mp[n/2]=f(n/2,m);
    else{
        mp[(n-1)/2]=f((n-1)/2,m);
        mp[(n-1)/2+1]=f((n-1)/2+1,m);
    }
    return mp[n];
}
int main(){
    fastio;
    ll n, m;
    cin>>n>>m;
    f(n,m);
    cout<<(mp[m]?"YES":"NO")<<endl;
    return 0;
}