BAEKJOON / 백준 - JAVA 16953번 A->B

2024.04.26기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 특정 연산을 통해 목표 값에 도달하는 문제입니다.

2가지 특정 연산이 있습니다.

1. 주어진 숫자 n에 곱하기 2
2. 주어진 숫자 오른쪽에 1을 추가

search() 메서드를 호출을 하여 문제를 해결했습니다.

search()는 시작 숫자가 목표 숫자와 같으면 연산 횟수를 반환합니다.

같지 않으면, 시작 숫자가 목표 숫자보다 작을 경우 곱하기 2 or 오른쪽에 1을 추가하는 연산을 수행합니다.

• 곱하기 2를 했을 때와 오른쪽에 1을 추가하는 경우를 재귀적으로 계산을 했습니다.
• 두 연산 결과가 모두 유효할 경우, 더 작은 연산 횟루를 반환합니다.
• 한 연산 결과만 유효한 경우 유효한 값만 반환합니다.

어떠한 연산애도 값이 만들어 지지 않는다면, 목표 값에 도달하지 못하여 -1을 반환하도록 되어 있습니다.

 

 

코드

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

public class Main {
	
	static long m;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Long.parseLong(st.nextToken());
		m = Long.parseLong(st.nextToken());
		long count = search(n, 1);
		
		bw.write(Long.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static long search(long n, long c) {
		long num = n;
		
		if (num == m) {
			return c;
		} else if (num < m) {
			long a = search(num * 2, c + 1); // 곱하기 2를 했을때, count는 +1
			long b = search(num * 10 + 1, c + 1); // 오른쪽에 1을 추가 했을때, count는 +1
			
			if (a != -1 && b != -1) { // 둘 다 값이 B가 되었을떄. 
				return Math.min(a, b); // 둘 중에 작은 값을 반환.
			} else if (a != -1 && b == -1) { // a만 값이 나왔을때.
				return a;
			} else { // b만 값이 나왔을때.
				return b;
			}
		}
		
		return -1;
	}
}