[백준/Baekjoon] 16953번 A->B (C++)

#include <iostream>
#include <algorithm>
using namespace std;

long long a, b;
long long min_count = 1000000000;
bool flag = false;

void dfs(long long a, long long cnt) {
    if (a > b) return;
    
    else if (a == b) {
        flag = true;
        min_count = min(min_count,cnt);
    } 
    
    else if (a < b) {
        dfs(a * 2, cnt+1);
        dfs((a * 10) + 1, cnt+1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> a >> b;
    
    dfs(a, 1);
    
    flag == false ? cout << "-1" : cout << min_count;
    return 0;
}

 

고려해야할 점 🤔

1. Greedy문제이므로 모든 경우를 탐색하는 것을 목표로 한다.
2. 여러가지 경우의 수가 있어도 가장 적은 count로 탐색하는 경우를 선택한다.

생각 정리 😤

1. 모든 경우를 탐색하는 경우를 그림으로 그려봤을 때, 한 깊이가 추가될 때 마다 수의 가장 끝에 1을 추가하는 것과 수를 2배 하는 2가지로 갈리는 것을 모두 탐색하는 과정은 그래프 탐색과 유사하다고 판단하였다. (사실 재귀와 더 유사한것 같기도.. 😅)
2. 그래프에서 가장 깊은 곳 까지 들어갔다가 조건에 부합하지 않으면 다른 방법을 시도 (방법이라 함은 수의 끝에 1을 추가하는 것과 수를 2배하는것.)
3. 정말 단순하지만 수의 가장 끝에 1을 추가하는 부분에서 고민이 있었다. (각자리의 수를 하나씩 10배 증가시키는 방법을 생각했는데 그냥 10배를 곱하고 1을 더하는 간단한 방법이 존재했다.!! 다음에 비슷한 문제에서 써먹어야겠다 🤣)
4. 알고리즘에서 삼항 연산자를 처음 써보았다. (swift와 작성 방법이 동일하다!! 매우 편리..🙂)
5. 전에는 코드가 길어지는 것, 변수가 많아지는 걸 매우 극혐했는데.. 가독성을 위해 flag 변수를 사용해서 나타내 보았다. (보기 더 좋은 것 같다. 안좋은 고정관념은 버려야겠다.)