[BOJ] 16953 A->B

A->B

풀이

• 걍 습관처럼 int[] 배열 만들어서 했는데 메모리초과 계속 남ㅡㅡ
• 1<=A<=B<=10^9 라는 조건이 있어서, 만약 *2 해주면 int 범위를 넘어갈 수도 있기 때문에 A,B를 long으로 받아야 한다고 함.
• bfs 로 풀었는데 dfs로도 풀 수 있는 듯
• 배열 안 만들고, Queue에 2 한 수, 10+1 한 수 더하면서 수가 B와 같아지면 break 하면 됨.
• 문제 조건을 잘 보자...^!!

BFS 코드

import java.util.*;
import java.io.*;
public class Main {
    static int answer;
    static long A,B;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        answer = 0;
        Queue<long[]> queue = new LinkedList<>();
        queue.add(new long[]{A,answer});
        while(!queue.isEmpty()){
            long[] cur = queue.poll();
            if(cur[0]==B) {
                answer = (int)cur[1];
                break;
            }
            //2곱한거
            long next = cur[0]*2;
            if(next>=0 && next<=B) queue.add(new long[]{next,cur[1]+1});
            //+1 한거
            next = cur[0]*10+1;
            if(next<=B) queue.add(new long[]{next,cur[1]+1});
        }
        if(answer==0) System.out.println(-1);
        else System.out.println(answer+1);
    }
}

DFS 코드

import java.util.*;
import java.io.*;
public class BOJ169536 {
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        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());
        dfs(A,B,0);
        if(answer == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(answer);
    }
    private static void dfs(long curr, long B, int cnt){
        if(curr == B) {
            cnt++;
            answer = Math.min(answer,cnt);
            return;
        }
        if(curr>B) return;
        dfs(curr*2,B,cnt+1);
        dfs(curr*10+1,B,cnt+1);
    }
}