[Java] 백준 16953.A → B

➡️문제 링크

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

 

 

💡아이디어

필요한 연산의 최솟값

그래프 탐색이다! 싶었다

뭔가 예전에 풀었던 숨바꼭질 느낌도 나고

 

 

✏️문제 풀이

1. BFS - 성공

나온 조건 그대로 곱하고, 오른쪽 자리에 1을 추가해 범위내, 방문 여부 확인하고 BFS 돌렸다

그리고 poll() 할 때, 해당 수가 B라면 BFS 종료 후 정답 출력

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		long A = Integer.parseInt(st.nextToken());
		long B = Integer.parseInt(st.nextToken());
		
		Deque<long[]> dq = new ArrayDeque<>();
		int limit = (int)Math.pow(10, 9);
		
		boolean [] visited = new boolean[limit+1];
		
		long result = Long.MAX_VALUE;
		dq.add(new long[] {A, 0});

		while(!dq.isEmpty()) {
			long [] point = dq.poll();
			
			if(point[0] == B) {
				result = point[1];
				break;
			}
			
			long n1 = point[0] * 2;
			long n2 = point[0]*10+1;
			
			long [] arr = {n1, n2};
			
			for(int i = 0; i < 2; i++) {
				long num = arr[i];
				if(num > limit) continue;	// 범위 체크
				if(visited[(int) num]) continue;	// 이미 방문
				
				visited[(int) num] = true;
				dq.add(new long[] {num, point[1]+1});
			}
					
		}
		
		if(result == Long.MAX_VALUE) System.out.println(-1);
		else System.out.println(result+1);

	}

}

 

 

 

 

2. 역순 - 성공

정답 확인 후, 다른 사람들의 풀이를 보는데, 시간이 거의 6~7배 차이가 났다

믿을 수 없는 광경을 목격하고 풀이를 보니, 나와 다르게 역순으로 접근해서 풀었다

다시 생각해보면, 

값은  "곱하기", "더하기" 이 두 연산으로 인해 계속 "증가"한다.

그러므로 계속 연산을 해줘야 하고 메모리도 많이 차지한다. 때문에 시간과 공간이 커지는 건 당연한 일이었다.

하지만, 역순으로 접근한다면, 값은 "감소" 해나가고, 나처럼 따로 배열도 필요하지 않기 때문에 사용되는 크기도 줄어든다.

package feb2026;

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

public class BJ_0223_16953 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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());
		
		int result = 1;
		
		// 둘 중 하나의 방법으로 만들어진게 확실할 때가 최적의 선택
		while(A < B) {
			if(B % 10 == 1) {	// A에 1을 추가해서 만든경우
				B /= 10;
			}else if(B%2 == 0) {	// A*2에 해당
				B /= 2;
			}else break;	// 둘 다 해당 안 됨
			result++;
		}	
		
		if(B == A) System.out.println(result);
		else System.out.println(-1);

	}

}

 

 

증가와 감소,

둘 중 어느 것을 기준으로 문제를 푸느냐에 따라

이렇게 결과가 차이 난다

감을 잡는 그 날까지 부지런히 풀어야지