[알고리즘 문제] 백준 16953번 A → B

16953번: A → B (acmicpc.net)

16953번: A → B

 

문제

 주어진 숫자 A에서 다음의 연산을 몇 번 거쳐야 B에 도달하는지 구하는 문제입니다.

 

 1. 2를 곱한다.

 2. 1을 수의 가장 오른쪽에 추가한다. (n * 10 + 1)

 

아이디어

 연산에 규칙성이 보이지 않으니 모든 경우를 해보는 수밖에 없습니다.

 그래프를 탐색하듯 1번과 2번 규칙을 각각 적용해보며 진행해 봅시다.

 

 1. 숫자 A에서 시작합니다.

 2. A에 1번 규칙을 적용시킨 경우와 2번 규칙을 적용시킨 경우를 나누어 연산 수를 재귀적으로 구합니다.

 3. A는 둘 중 더 적은 수의 규칙 + 1을 통해 도달 가능합니다.

     둘 모두 도달할 수 없다면 A도 도달할 수 없습니다.

 

 이번 문제의 연산은 모두 커지는 연산이기에 실패한 갈래를 쉽게 알 수 있습니다.

 

 4. 만약 현재 수가 목표 수 보다 크면 도달할 방법이 없습니다.

 

코드

// No.16953 A->B

#include <iostream>
using namespace std;

const int NOPE = 10000;

int solve(uint64_t from, uint64_t to) {
    if (from > to) {
        return NOPE;
    } else if (from == to) {
        return 0;
    }

    int route1 = solve(from * 2, to);
    int route2 = solve(from * 10 + 1, to);

    return route1 < route2 ? route1 + 1 : route2 + 1;
}

int main(void) {
    int from, to;
    cin >> from >> to;
    int answer = solve(from, to);

    if (answer >= NOPE)
        cout << -1;
    else
        cout << answer + 1;
}

 

기타

 상수 NOPE을 두어 불가능한 경우를 만들었습니다.

 두 경로 중 더 짧은 경로를 선택하는 과정에서 -1 값이 섞이면 경우를 나누어야 해서, 편의상 큰 값을 대신 사용했습니다.

 2^30 = 약 10.7억으로 답이 30을 넘길 일은 없습니다.