[알고리즘] A → B - 백준 16953

A → B 성공

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	31247	13014	10422	40.171%

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

100 → 200 → 2001 → 4002 → 40021

 

과정

처음에는 12904의 A와 B, 1463의 1로 만들기를 생각하면서 풀었다.

갑자기 BFS, Queue에 얽매여서 헤메다가 그냥 에라이 하고 문제를 그대로 흐름에 맞춰서 구현했는데, 정답이여서 놀랐다.

알고 보니, 다른 방식으로의 풀이가 많은 문제였다. dp로 푸는 경우도 있다고 하더라.

 

결과

//
// Created by 전시은 on 2023/02/15.
//
// 문제 :: A → B
// 링크 :: https://www.acmicpc.net/problem/16953
// 입력 :: 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
// 출력 :: A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.


#include <iostream>
using namespace std;


int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int nA, nB, nCount = 0;
    cin >> nA >> nB;

    while (1)
    {
        // 결과값 없음
        if (nA > nB)
        {
            cout << -1;
            break;
        }
        // 결과값 : 카운트
        if (nA == nB)
        {
            cout << nCount + 1;
            break;
        }

        // 끝에서부터 접근한다.
        // 10을 곱하고 1을 붙이므로 나머지가 1이 되거나
        if (nB % 10 == 1)
        {
            nB /= 10;
        }
        // 2로 곱해서 값이 만들어지는 경우
        else if(nB % 2 == 0)
        {
            nB /= 2;
        }
        // 그렇지 않으면 완성할 수 없는 값.
        else
        {
            cout << -1;
            break;
        }
        nCount++;
    }

    return 0;
}