97. 백준 16953 번 C++ 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 BOJ 16953 번 A → B 입니다.

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

16953번: A → B

 

먼저 백준 16953 번 C++ 정답 코드입니다. 설명은 아래에 있습니다.

#include <iostream>
using namespace std;

int main(){
    int A, B, cnt = 1;
    cin >> A >> B;
    while (A != B){
        cnt++;
        if (B % 10 == 1) B /= 10;

        else if (B % 2 == 0) B /= 2;

        else{
            cnt = -1;
            break;
        }
        if (B < A) {
            cnt = -1;
            break;
        }
    }
    cout << cnt;

    return 0;
}

 

문제 요약

 

숫자 A 에 2 또는 가장 마지막 자리에 1을 붙여서 B로 최소 횟수 + 1을 출력

만약 불가능하다면 -1 출력

 

문제 접근

A의 마지막 자리에 1을 붙이는 건 어려우므로

B의 마지막 자리에서 1을 빼거나 2를 나눠 A와 같게 만들기

 

C++ 코드 구현

A, B를 입력 받습니다.

cin >> A >> B;

 

연산 횟수를 측정하면서

1. B의 마지막 자리가 1이면  10으로 나누고 나머지를 버려 B의 마지막 1의 자리를 없앱니다.

2. B가 2로 나눠지면 2로 나눠 B를 B/2로 만듭니다.

cnt++;

if (B % 10 == 1) B /= 10;

else if (B % 2 == 0) B /= 2;

 

만약 위의 연산중 어떤것도 작동하지 않으면 B는 A 가 될 수 없으므로 -1을 출력합니다.

(while문이 실행된 순간부터 A != B 라는것이 확실해집니다.)

else{
    cnt = -1;
    break;
}

 

혹은 B가 A보다 작다면 

B는 A 가 될 수 없으므로 -1을 출력합니다.

if (B < A) {
    cnt = -1;
    break;
}

cout << cnt;

 

백준 16953 번 A → B C++ 최종 코드입니다.

#include <iostream>
using namespace std;

int main(){
    int A, B, cnt = 1;
    cin >> A >> B;
    while (A != B){
        cnt++;
        if (B % 10 == 1) B /= 10;

        else if (B % 2 == 0) B /= 2;

        else{
            cnt = -1;
            break;
        }
        if (B < A) {
            cnt = -1;
            break;
        }
    }
    cout << cnt;

    return 0;
}

 

백준 16953 번 A → B 자세한 설명 및 C++ 코드였습니다.

감사합니다.