[백준](Java) 16953 - A->B

민지킴·2021년 6월 1일
0

백준

목록 보기
24/48
post-thumbnail

문제 링크

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

문제 풀이

지난번엔 죽어도 못풀겠더니 생각보다 간단하게 풀었다.
dfs를 통해서 *2를 하거나, 1을 뒤에 붙이는 로직으로 각각 뻗어나가게 했고
m 보다 크거나 같아지면 return 하도록 하였다.

값의 범위가 크므로 int가 아니라 long으로 처리할것!


코드

import java.util.*;

public class Main {

    static long m;
    static long answer = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        m = sc.nextInt();

        dfs(n,1);

        System.out.println(answer==Integer.MAX_VALUE ? -1 : answer);
    }

    public static void dfs(long n,long res) {
        //System.out.println(n + " "+ res);
        if (n >= m) {
            if(n==m){
                answer = Math.min(res,answer);
            }
            return;
        }

        for(int i=0; i<2; i++){
            if(i==0){
                dfs(n*2,res+1);
            }else{
                dfs(n*10+1,res+1);
            }
        }


    }
}


profile
하루하루는 성실하게 인생 전체는 되는대로

0개의 댓글