[백준 16953] A → B (JAVA)

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

16953번: A → B

 

문제 분석을 하자면 정수 A 에서 2배를 하거나 뒤에 1을 붙이는 두가지 방법만을 사용해서 정수 B로 바꿀수 있는 경우

몇 회의 시행으로 바꿨는지를 출력, 바꿀수 없는 경우 -1을 출력하면 되는 문제이다.

 

이 문제를 풀때의 아이디어는 A 에서 B로 바꾸는 과정을 탐색을 통해 하나씩 체크하면서 가도 되지만

그보다는 B에서 A로 바꾸는 과정을 탐색하면서 가는것이 더 이득이라는 것을 이용했다.

 

풀이방식은 다음과 같다.

 

B → A 

1. 현재 B가 짝수인경우 2로 나눈다.

2. 현재 B의 1의 자리수가 1인 경우 1을 제거한다.

 

1 또는 2를 반복해서 시행하고 A와 일치하는 경우엔 탐색을 종료하고 시행횟수를 출력한다.

반복해서 시행중 조건 1,2 모두 만족하지 않는 경우 탐색을 종료하고 -1을 출력한다.

 

그럼 이 과정을 코드로 구현 해보겠다.

 

시행횟수, a ,b 를 선언해준다.

 

	static int a,b,depth = 1;

 

 

2번 조건의 1의 자리수가 1인 경우를 아는 방법은 10으로 나눈 나머지가 1이면 되기 때문에 나머지 연산자를 사용한다.

이를 토대로 반복문을 통해 간단히 메소드를 구현 할 수 있다.

 

	static int bfs() {
		int now = 0;
		
		while(now != b) {
			now = b;
			if(b%2 == 0) {
				b/=2;
				depth++;
			}else if(b%10 == 1) {
				b = (b - 1)/10;
				depth++;
			}
			if(a == b) return depth;
		}
		
		return -1;
	}

 

 

예제를 실행해보면 정확한 답을 내는것을 알 수 있다.

 

 

아래는 코드의 전문이다.

 

package boj3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj16953 {
	
	/* B -> A 로 진행
	 * B가 짝수인경우 2로 나눔
	 * 아닌 경우 마지막 자리 1이라면 1제거
	 * 마지막 자리가 1인건 10으로 나눈 나머지로 알 수 있음
	 * 반복중 A와 일치하면 반복횟수 리턴
	 * 탐색종료되면 -1 리턴
	 */
	
	static int a,b,depth = 1;
	
	static int bfs() {
		int now = 0;
		
		while(now != b) {
			now = b;
			if(b%2 == 0) {
				b/=2;
				depth++;
			}else if(b%10 == 1) {
				b = (b - 1)/10;
				depth++;
			}
			if(a == b) return depth;
		}
		
		return -1;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		
		in.close();
		
		System.out.print(bfs());
	}

}