[백준] 16953번 : A → B - C/C++

 

문제를 보고 A → B 이렇게 가는건 너무 경우의 수가 많지 않은가?

라는 생각을 했다.

하지만 반대로 B → A 의 수는 연산의 횟수가 적을 것이라고 생각할 수 있다.

 

그러니, 우리는 위와 같은 아이디어로 문제를 풀어나갈 수 있다.

 

B → A 를 생각해보자.

1. 짝수라면 2로 나누기
2. 끝자리가 1이라면 1을 제외시키기
3. 1번과 2번에 속하지 않는다면 -1 출력

1번과 2번을 코드로 바꾸면 아래처럼 작성할 수 있다.

더 깔끔한 코드가 있을 수 있겠지만, 필자는 이렇게까지가 최선이다.

while(a < b){
    if(b % 2 == 0){
      b /= 2;
     } else {
       	if(b % 10 == 1){
          b /= 10;
        } else {
         break;
        }
     }   
   cnt ++;
}

 

b가 짝수라면 2로 나누기. (가능한 연산이 곱하기 2, 맨 끝자리에 1 추가하기 뿐이니..)

if(b % 10 == 1) 이 부분이 끝자리가 1일 때 제거하는 방법. (왜 끝자리가 1이냐면, 1만 추가할 수 있으니까.)

 

이렇게 핵심 부분의 코드는 모두 작성했다.

위의 while 문 조건에서 아무것도 걸리지 않는다면, "-1" 을 출력해야한다.

 

 

 

전체 코드

#include <iostream>

//A → B
using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    int cnt = 1;

    while(a<b){
        if(b%2==0){
            b /= 2;
        } else {
            if(b %10 == 1){
                b /= 10;
            } else {
                break;
            }
        }   
        cnt ++;
    }
    if(a!=b){
        cout << "-1" << '\n';
    } else {
        cout << cnt << '\n';
    }
}

 

 

코드의 길이가 30줄도 안된다.

실버2 난이도의 문제였다. 16953번의 문제 풀이 아이디어는 '반대로 생각하기'인 것 같다.

A → B 만 생각하다보면 경우의 수도 많고, 코드로 어떻게 구현해야할지 모르겠는데

B → A 로 반대로 생각하니 조금은 쉽게 풀렸던 것 같다.

반대로 생각할 수 있어도 코드를 어떻게 작성할까 고민을 많이 했던 문제였던 것 같다.

어려운 함수를 쓴 것도 아니고 코드에서 쓰인 것이라고는 사칙연산 뿐이다.

컴퓨터적 사고를 더 키우자.

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️