[C++][백준 BOJ]16953_A->B.

문제 번호

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

16953번: A → B

 

 

 

알고리즘 분류

 그리디(greedy). 그래프(BFS).

 

문제 풀이

 A에서 B를 만드는 규칙을 찾지못하여서 꺼꾸로 B에서 A를 만들어보기로 하였다. 

A에서 B로 갈때의 규칙은

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

이렇게 두가지 이다.

 

따라서 B에서 2를 나누거나 B에서 1을 뺴고 10으로 나누거나 해서 A를 만들 수 있는지 확인해보기로 하자.

B가 A랑 같아지면 A->B는 가능하다.

if(B==A)
            break;

B가 A보다 작아진다면 A->B는 불가능하다.

 if(B < A)
            return -1;

마지막으로 문제에서 주어진 두가지 규칙외에 다른 방법은 없음으로 두가지 조건을 검사하되, 그외에 방법이 필요하다면 A->B는 불가능하다.

       if(B % 10 == 1)
        {
            B -= 1;
            B /= 10;
            answer++;
        }
        else if(B % 2 == 0)
        {
            B /= 2;
            answer++;
        }
        else
            return -1;

전체코드

#include<iostream>
using namespace std;

int Solution(int A, int B)
{
    int answer = 1;

    while(1)
    {
        if(B==A)
            break;

        if(B < A)
            return -1;

        if(B % 10 == 1)
        {
            B -= 1;
            B /= 10;
            answer++;
        }
        else if(B % 2 == 0)
        {
            B /= 2;
            answer++;
        }
        else
            return -1;
    }

    return answer;
}

int main()
{
    int A,B; cin >> A >> B;
    cout << Solution(A,B) << '\n';

    return 0;
}

특이사항

 문제에서 연산횟수에 맨 처음 숫자도 포함시켰다. 

2 → 4 → 8 → 81 → 162 이라면 화살표의 개수인 4번이 정답이 아니라 5가 정답이다.