백준 16953 - A -> B [C/C++]

16953번: A → B (acmicpc.net)

문제 설명 및 입력과 출력

 

 매우 간단한 문제이다. 자주 써왔던 케이스 분류와 재귀를 쓰면 쉽게 풀릴 것이라는 생각을 했고, 그대로 코드를 썼더니 그냥 맞혔다.

 

 그나마 사용된 슥삭 프로그래밍이라고는 곱하기 2는 그냥 비트연산자 "<<" left shifting으로 처리해주었고, 뒤에 1 더해주는 것은 to_string 함수와 stoll 함수로 형변환을 자유롭게 움직일 수 있게 해준 것이 다이다.

 

 긴 말 필요없이 코드를 보면 이해가 갈 것이다. 그냥 재귀로 돌면서 1을 더해준 것과 2를 곱해준 두 가지 경우의 수로 계속 가지를 치면서 나가주면 된다.

 

#include <iostream>
#include <string>

using namespace std;

long long int first, latter;
long long int tryCount = -1;

void checkPossiblethings(long long int num, long long int cnt){
    if (num > latter)
        return;
    else if (num == latter){
        tryCount = (tryCount==-1) ? cnt : min(cnt, tryCount);
        return;
    }
    else{
        checkPossiblethings(num << 1, cnt+1);
        string addednum = to_string(num)+"1";
        checkPossiblethings(stoll(addednum), cnt+1);
    }
}

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

    cin >> first >> latter;
    checkPossiblethings(first, 0);
    tryCount = (tryCount==-1) ? -1 : tryCount+1;
    cout << tryCount << '\n';

    return 0;
}