[BOJ] 16953 - A → B

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

BOJ - A → B

문제 유형: 그리디, BFS, DFS

문제 난이도: Silver II

시간 제한: 2초

메모리 제한: 512MB

 

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

 

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

풀이

B에서 A로 역변환하는 경로는 단 하나 뿐이므로, B에서 만들어볼 수 있다.

예를 들어, b가 2의 배수인 동안, 2로 나누고, 일의자리수가 1이면 10으로 나누면 되겠다. 그 외의 경우에는 -1을 출력하면 된다.

 

그게 아니라면, BFS나 DFS로 풀 수 있다.

이진 트리를 순회한다고 생각하고, 하나의 자식에는 현재 수에 2를 곱한 값, 다른 자식에는 현재 수에 10을 곱하고 1을 더한 값으로 한다.

이렇게 a부터 순회를 하다가, 노드의 키가 b를 넘으면, 유효하지 않으므로 1을 반환한다.

BFS가 DFS보다 더 적합하다. BFS는 가중치가 없다는 전제하에, 항상 시작점으로부터 최단거리이기 떄문이다.

물론, 본인은 DFS를 먼저 떠올리고 풀어서, 아래에는 DFS만 제공한다. BFS나 그리디는 사실 더 구현이 쉽다.

 

코드

C++

(dfs)

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll a, b;

ll solve(ll curr) {
  if (curr > b) {
    return -1;
  }
  if (curr == b)
    return 1;
  ll minDepth = INT_MAX;
  ll res = solve(curr * 2);
  if (res != -1) {
    minDepth = min(minDepth, res + 1);
  }
  res = solve(curr * 10 + 1);
  if (res != -1) {
    minDepth = min(minDepth, res + 1);
  }

  return minDepth == INT_MAX ? -1 : minDepth;
}

int main(int argc, char *argv[]) {
  cin >> a >> b;

  ll res = solve(a);
  cout << res << "\n";

  return 0;
}