[C++] 백준 온라인 저지 16953번 A -> B 풀이

A에서 B로 만드는 데 필요한 최소 연산 횟수를 구하는 문제

 

---

 

문제의 조건

 

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

 

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

 

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

 

입력

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

 

출력

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

 

 

풀이 과정

 

 처음엔 DP로 풀 수 있을까 해보다가... 각이 안 나와서 구글링 한 문제 ㅠㅠ

 이 문제의 키포인트는 거꾸로 생각하는 것 이었습니다...!!!!! B에서 2로 나누거나 1을 빼고 10으로 나눠가며 A를 만들어 가면서 횟수를 세는 것이었죠... 즉 가능한 경우는

 

1. 2로 나눠질 때(짝수일 때) => 2로 나눈다.

2. 10으로 나눈 나머지가 1일 때 => 10으로 나눈다. 

 

 위 두 가지 경우일 때에만 연산을 하고 나머지에는 -1을 출력하면 되는.. 그런 문제였습니다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[])
{
    int A, B;
    cin >> A >> B;
    
    int answer = 0;
    while (A < B)
    {
        if (0 == B % 2)
            B /= 2;
        else if (1 == B % 10)
            B /= 10;
        else
            break; //어느 연산도 가능하지 않으면 반복문 탈출
        answer++;
    }
    
    //반복문이 끝났을 때 A == B 이면 정답에 1 더한 값을 출력하고
    if (A == B)
        answer++;
    else //아니라면 -1 출력 
        answer = -1;
    
    cout << answer;
    
    return 0;
}