[백준] 16953번: A -> B / C++

✏️ 문제 링크

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

16953번: A → B

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

1. DFS는 경우가 현재 숫자에서 경우가 2를 곱하거나 1을 더해주는 경우인데, dfs를 재귀로 계속 들어가다가 만약 cur이 B와 같아지는 순간이 오면 멈추면 된다. 

 

2. 거꾸로 탐색하는 건데 사실 내가 처음에 떠올렸던건 이 방법.. dfs로도 될것 같았지만 이 방법으로도 될것 같아서 해봤다..ㅎㅅㅎ그랬더니 되네 성능 차이는 dfs와 얼마 나지 않는 것 같다 

 

 

✏️ 문제 코드 (DFS)

#include <bits/stdc++.h>
using namespace std;

long A, B, answer=10000000;

void dfs(long cur, long depth){
    if(B<cur) {return;}
    
    if(cur==B){
        answer= min(answer, depth); return;
    }
    
    dfs(cur*2, depth+1);
    dfs((cur*10)+1, depth +1);
}
int main(){
    cin>>A>>B;
    dfs(A,1);
    
    cout<<(answer==10000000? -1:answer)<<"\n";
    return 0;
}

 

✏️ 문제 코드(거꾸로 되돌아가며 답을 구하는 코드)

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    long A, B; cin>>A>>B;
    long answer=1;
    while(B>=A){
        if(B==A) {
            cout<<answer;
            return 0;
        }
        answer++;
        if(B%2==0){
            B/=2;
        }else if(B%10==1){
            B-=1;
            B/=10;
        }else
            break;
    }
    cout<<-1<<"\n";
    
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐