[C++] 16953 A->B

C++ / 실2 / 그리디 알고리즘

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

 

20분만에 푼 문제이다. 1을 끝에 추가하는 게 아닌 2를 추가하는 문제였다면 너비 우선 탐색을 사용하여 풀어야 하는 더 복잡한 문제가 됐을 것 같다.

매 순간 최선의 선택을 하는 그리디 알고리즘을 사용하여 문제를 풀었다. 짝수라면 한번 나누고 횟수를 올리고, 1의자리 수가 1이라면 1을 뺀 수를 만들고 횟수를 올렸다. 

정상적으로 통과하여 while문을 조건 때문에 나온 경우라면 A==B일테니, 그렇다면 횟수를 출력하고 A!=B라면 -1을 출력하도록 했다.

 

다음은 전체 코드이다.

#include <iostream>
using namespace std;

int main() {
    int A, B;
    int ans = 0;

    cin >> A >> B;

    while (B > A) {
        if (B % 2 == 0) {
            B /= 2;
            ans++;
        }
        else if (B % 10 == 1) { 
            B--;
            B /= 10;
            ans++;
        }
        else{
            break;
        }
    }
    if (A == B) {
        cout << ++ans;
    }
    else {
        cout << -1;
    }
}