[백준] 16953 A → B - DFS(깊이우선탐색) JAVA

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

16953번: A → B

코드설명

DFS(깊이우선탐색) 문제입니다.

 

처음에 문제를 읽고, DFS 혹은 BFS를 통해 구현할 수 있다는 것은 어렵지 않게 알 수 있습니다.

하지만, A, B (1 ≤ A < B ≤ 10^9) 의 범위에 의해서, 2를 곱하는 경우와, 1을 수의 가장 오른쪽에 추가하는 경우 2가지에서 2^(10^9) 이라 생각하여 시간초과가 나타날 수 있을 것 이라 생각하여 최적 부분 구조를 만족하는 구조의 함수임을 알 수 있어서, 재귀와 메모이제이션을 활용했습니다.

 

하지만, 메모리초과가 발생합니다. (속도측면에서는 빠를 것 입니다, 이유는 탐색공간이 10^9 으로 강제되기  시간복잡도가 10^9 이 되기 떄문 )

이유는, CACHE = NEW INT[ 1e9 + 1 ] 로 최대값이 들어올경우에는 

INT형의 자료형 크기 : 4BYTE (32BIT)

1e9 + 1 * 4 BYTE 를 할경우 대략 4000MB 가 나옵니다. (여기서 1 KB = 1000 BYTE라고 가정합니다. 원래는 2^10 BYTE이지만, 근사값으로 설정합니다.)

4000MB 면 4GB입니다. 

 

메모리 크기를 예측하지 못하고, CACHING을 사용하려했습니다만, 실패했습니다.

이런 예측을 하지 못한 근본적인 이유는, 시간복잡도를 잘못 계산했기 떄문입니다.

저는 완전탐색으로 진행할경우 두 가지 선택이기에 2^(10^9)) 이라 생각했지만, 해당 숫자에 1을 더하는게 아닌,

실제로 선택하는 방법은 2를 곱하는 경우와 1을 수의 가장 오른쪽에 추가하는 경우이기에 

실제로 계산하는 개수는 훨씬 줄어듭니다.

실제로 위의 시간복잡도를 계산해봅시다. B의 최대값은 10^9 이라고 가정하고, A의 시작값을 1 이라고 가정합니다.

- 2를 곱하는 연산의 최대 횟수는 LOG(10^9) = 30 입니다.

- 1을 추가하는 연산의 최대횟수는 약 9 입니다. (10^9의 자릿수임)

이떄 정말 최악의 경우 O(2^39)가 발생하는 것 아니냐? 라고 할 수 있습니다.

하지만, 실제로는 B값을 생각보다 빠르게 넘어가면서 시간초과가 발생하지 않습니다. ( 이유는 중복상태가 발생하지 않기에 그런것인데요, 정확히 어떤 POINT인지 확실한 이해가 되지는 않아 설명이 불가합니다. )

 

 

두번째로, 유의해야할점은,

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.  이기에 long 타입으로 계산해야합니다.

이떄 왜 10^9인데 INT형을 사용하면 안되는가? 라는 생각이 듭니다. 이유는 B값(10^9)보다 크면 애초에 중단시키는데 말입니다.

반례를 제시해보겠습니다.9*10^8 이 주어졌다고 가정합니다. 이떄 2*9*10^8 이 곱해질경우에는 안전합니다.10*9*10^8 + 1이 될경우에는?  90억 + 1 이 되면서 INT형의 범위 21억(2^31 - 1)을 초과합니다.

 

 

또한, 종료조건으로는 예시로 A = 1, B = 3 이라고할떄, 해당예제는 불가능하므로 바로 종료시키고 -1 을 출력시켜야합니다.

1 3

코드

정답코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B;
	static int answer = 0;
	static int[] arr;
	static int MAX = (int) 1e9 + 1;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		System.out.println( (answer = DFS(0, A, B)) >= MAX ? -1 : ( answer + 1));
	}
	
	static int DFS(int depth, long now, long target) {
		if(target == now) return 0;
		if(target < now) return MAX;

		int ret = MAX;
		//2를 곱하는 경우.
		ret = DFS(depth + 1, now * 2, target) + 1;
		
		//1을 수의 가장 오른쪽에 추가하는 경우
		ret = Math.min(ret, DFS(depth + 1, now * 10  + 1, target) + 1);
		return ret;
	}
}

 

처음에 제출했던 메모리초과 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B;
	static int answer = 0;
	static int[] arr;
	static int MAX = (int) 1e9 + 1;
	static int[] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		cache = new int[B + 1];
		Arrays.fill(cache, -1);
		
		System.out.println( (answer = DFS(0, A, B)) >= MAX ? -1 : ( answer + 1));
	}
	
	static int DFS(int depth, int now, int target) {
		if(target == now) return 0;
		if(target < now) return MAX;

		if(cache[now] != -1) return cache[now];
		int ret = MAX;
		//2를 곱하는 경우.
		ret = DFS(depth + 1, now * 2, target) + 1;
		
		//1을 수의 가장 오른쪽에 추가하는 경우
		ret = Math.min(ret, DFS(depth + 1, now * 10  + 1, target) + 1);
		
		return cache[now] = ret;
	}
}

 

 

B에서 A로 가는 방식을 구현한 코드입니다.

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


public class Main {
	
	public static String A,B;
	public static long answer = 1;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	A = st.nextToken();
    	B = st.nextToken();	
    	
    	while(B.length() > 0) {
    		long parsedLong_B = Long.parseLong(B);
    		char lastCharAt_B = B.charAt(B.length() - 1);
    		
    		if( !( lastCharAt_B == '1') && !( parsedLong_B %2 == 0)){
    			break;
    		}
    		if( lastCharAt_B == '1') {
    			B = B.substring(0, B.length() - 1);
    			answer++;
    		}
    		else if( parsedLong_B %2 == 0) {
    			B = String.valueOf( parsedLong_B / 2);
    			answer++;
    		}
    		
    		
    		if(A.equals(B)) {
    			System.out.println(answer);
    			return;
    		}
    	}
    	System.out.println("-1");
    }
    
    
}