제1회 춘배컵에 나온 문제다.
춘배는 귀엽다!! 나비도 귀엽다!!
![](https://t1.daumcdn.net/keditor/emoticon/friends1/large/003.gif)
체감 티어 : 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;
}
'BOJ' 카테고리의 다른 글
BOJ 10975 - 데크 소트 2 (0) | 2023.11.07 |
---|---|
BOJ 29792 - 규칙적인 보스돌이 (1) | 2023.11.01 |
BOJ 1150 - 백업 (1) | 2023.10.28 |
BOJ 5910 - Mountain Climbing (1) | 2023.10.27 |
BOJ 18042 - Assimilation (0) | 2023.10.26 |