백준 16953번 : A -> B (C 언어)

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

16953번: A → B

Code:

#include <stdio.h>
#include <limits.h>
 
int min = INT_MAX;
int cnt = 0;
long long a, b;
int flag = 0;
 
void dfs(long long a, int cnt)
{
    if (a > b)
    {
        return;
    }
    if (a == b)
    {
        min = (min > cnt) ? cnt : min;
        flag = 1;
    }
    dfs(2 * a, cnt + 1);
    dfs(10 * a + 1, cnt + 1);
}
 
int main()
{
    scanf("%lld %lld", &a, &b);
    dfs(a, 1);
    if (flag == 1)
    {
        printf("%d", min);
    }
    else
    {
        printf("-1");
    }
}
 

문제풀이:

1. a와 b의 값을 scanf로 받는다.

2. DFS를 이용해서 전체 탐색을 한다.

경우가 2가지 이므로

 dfs(2 * a, cnt + 1);

dfs(10 * a + 1, cnt + 1);

를 이용해 전체적으로 탐색.

3. a==b가 같을 때 작은 수가 필요하므로 비교하여 저장.