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

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

🥈실버 2

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

16953번: A → B

---

접근

거꾸로 생각해본다.

 

2 162 예의 경우

 

2 → 4 → 8 → 81 → 162

 

위와 같이 흘러가는데, 거꾸로 하면

162 -> 81 -> 8 -> 4 -> 2와 같이 흘러간다.

 

 

이렇게 보면 규칙을 쉽게 찾을 수 있다.

1. B가 2로 나눠지는 경우 2로 나누고 count++
2. B가 2로 안나눠지는데 맨 오른쪽에 1이 있으면 1지우고 count++
3. B가 2로 안나눠지는데 맨 오른쪽에 1도 없으면 그냥 안되는 거라서 -1 출력 후 프로그램 종료

 

예제 케이스 4 42를 거꾸로 하면 다음과 같이 흘러간다.

 

42 -> 21 -> 2 ?   => -1 출력

 

A를 4, B를 42로 잡았을 때, B가 A보다 작아지는 경우 반복문에서 빠져나오고 -1을 출력하는 것으로 판단할 수 있었다.

 

위 규칙을 순서도로 그리면 대충 다음과 같다.

 

 

추가로 A==B 상황에서 count값을 그대로 출력하면 안된다.

 

162 -> 81 -> 8 -> 4 -> 2

 

잘 보면 count가 4번 올라가는 것을 확인할 수 있다.count를 0으로 선언했다면 count+1을 출력 해야한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int main() {
  string A, B;
  cin >> A >> B;
  int cnt = 0;

  while ( stoi(A) < stoi(B) ) {
    if (stoi(B) % 2 == 0) {
      B = to_string(stoi(B) / 2);
      cnt++;
    }
    else {
      if (B[B.length()-1] != '1') {	// 맨 오른쪽이 1이 아니면 -1 출력 후 종료
        cout << -1;
        return 0;
      }
      B.erase(B.end()-1);	// 맨 오른쪽이 1이면 B의 맨 오른쪽 값 지우기
      cnt++;
    }
    if (A == B) {	// 위의 연산이 끝났을 때 cnt+1을 출력 후 종료
      cout << cnt+1;
      return 0;
    }
  }
  cout << -1;
  return 0;
}