[Java] BOJ16953, 백준 - A → B

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

16953번: A → B

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	9006	3873	3085	41.326%

문제

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

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

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

 

입력

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

 

출력

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

 

 

<풀이>

연산을 두 가지 할 수 있는데, 2를 곱하는 연산과 1을 추가하는 연산이다.

이걸 앞에서부터 찾느냐 뒤에서부터 찾느냐 비교해보면 아주 큰 차이가 있는데,

• A → B로 찾는 경우

그러면 가능한 연산이 뒤에 1을 붙히는 연산과 2를 곱하는 연산 두 가지가 있다.

일단 고려해야하는 연산이 두 가지인데다가 연산을 해도 어떤 것을 써야할지 모르니 일일히 저장해줘야된다.

10^9까지가 B의 범위인데, 1에서 출발해서 2를 곱해서 10^9에 도달하려면 약 30번을 곱해줘야한다.

1을 추가해서 가는 경우도 9번

어찌저찌 시간제한에 걸린다고 하더라도 풀이부터 복잡한게 눈에 뻔하다.

그러니 반대로 생각해보자.

 

• B → A로 찾는 경우

가능한 연산은 뒤에서 1을 빼는 연산과 2로 나누는 연산이다.

두 연산을 동시에 할 수 있는 조건이 없기 때문에(맨 끝자리가 1인 숫자를 2로 나눌 수 없음. 반대도 마찬가지)

조건을 만족하는지 개별적으로만 검사해주면 된다.

게다가 이 두 연산을 할 수 없는 경우에는 실패한 것이니, 고려해야 할 것은

2로 나눌 수 있느냐, 맨끝자리가 1이냐, 둘 다 못하냐 이것밖에 없다.

그러면 연산을 아무리 많이 해봐야 30번

그러므로 B부터 거꾸로 찾아보도록 하겠다.

 

1. B에서 가능한 연산을 수행한다.
   1. B를 2로 나눌 수 있는 경우 > 2로 나눠준다
   2. B의 맨 끝자리가 1인경우 > 1로 빼준다
   3. 두 연산의 연관성이 없기 때문에 배열 등으로 최솟값을 저장해줄 필요가 없이, 그냥 가능한지만 판단하면 됨
2. 종료조건
   1. 가능한 연산이 없는경우
   2. B가 A보다 작아진 경우
3. 출력
   1. B를 A로 만들었으면 cnt를 출력(A==B)
   2. 그렇지 못했으면 "-1" 출력

 

소스코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 입력부
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		// 맨 끝자리를 2로 나눌 수 있는 경우에는 2로 나눔
		// 없는 경우(1인 경우)에는 1을 제거
		int cnt = 1;

		while (b > a) {
			if (b % 2 == 0)
				b /= 2;
			else if (b % 10 == 1)
				b /= 10;
			else
				break;

			cnt++;
		}

		if (a == b)
			System.out.println(cnt);
		else
			System.out.println("-1");
	}
}

풀이만 생각한다면 아주 쉬운 문제