[백준][boj] A → B(16953) - JAVA

문제 파악

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

 

 

 

 

접근 방법

bfs를 통해 접근하면 어떨까?

1. 2를 곱하는 경우
2. 1을 을 수의 가장 오른쪽에 추가하는 경우

• 두 가지의 경우의 수를 큐에 넣어 준 다음, 만약 a가 b와 같게 된다면 answer를 갱신하고, 반복문을 종료하였다.
• 무한 루프의 반복을 막기 위해, 다음 수가 b값을 넘지 않는 조건에서만 큐에 다음 수를 넣어주었다.

 

 

코드 구현

첫번째 코드(틀린 코드)

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException{
        
        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 answer = Integer.MAX_VALUE;
        
        Deque<int[]> q = new ArrayDeque<>();
        q.offerLast(new int[]{a,0});

        while(!q.isEmpty()){
            int [] curr = q.pollFirst();
            
            int curr_a = curr[0];
            int count = curr[1];

            if(curr_a == b){
                answer = Math.min(answer, count);
            }
            
            if(curr_a * 2 <= b){
                q.offerLast(new int[]{curr_a*2,count+1});
            }
            if(curr_a*10 + 1 <= b){
                q.offerLast(new int[]{curr_a*10+1,count+1});
            }
        }

        if(answer == Integer.MAX_VALUE){
            System.out.println(-1);
        }else{
            System.out.println(answer+1);
        }
    }
}

 

 

정답코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken()); // long 자료형으로 변경
        long b = Long.parseLong(st.nextToken());
        int answer = -1;

        Deque<long[]> q = new ArrayDeque<>(); // 큐에서 long[] 사용
        q.offerLast(new long[]{a, 1});

        while (!q.isEmpty()) {
            long[] curr = q.pollFirst();

            long curr_a = curr[0];
            int count = (int) curr[1];

            if (curr_a == b) {
                answer = count;
                break;
            }

            if (curr_a * 2 <= b) {
                q.offerLast(new long[]{curr_a * 2, count + 1});
            }
            if (curr_a * 10 + 1 <= b) {
                q.offerLast(new long[]{curr_a * 10 + 1, count + 1});
            }
        }
        System.out.println(answer);
    }
}

→ 처음 코드가 4%에서 자꾸 오류가 나 int형을 long형으로 모두 바꾸어주었다 !

문제에서 발생하는 두 가지의 연산 중,

(1) A * 2
최대값: A×2≤2×109=2,000,000,000, int 범위 (2,147,483,647)를 초과하지 않으므로,
A * 2는 int로 충분히 처리 가능 !

(2) A * 10 + 1 (오버플로우 발생)
최대값: A×10+1≤10×109+1=10,000,000,001, int 범위 (2,147,483,647)를 초과하므로, long이 필요

 

 

 

자료형을 틀리신 다른 분들을 위한 테스트셋

500000000 705032705
잘못된 출력 값: 2
답: -1

 

 

 

 

다른 사람 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in)
        );
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        int count = 1; // 이미 B가 초기 상태이므로 연산 횟수를 1부터 시작
        while (B > A) {
            // 1) B가 10으로 끝나는 수(일의 자리가 1)이면 (B-1)/10
            if (B % 10 == 1) {
                B = (B - 1) / 10;
                count++;
            }
            // 2) B가 짝수이면 B /= 2
            else if (B % 2 == 0) {
                B /= 2;
                count++;
            }
            // 3) 그 외에는 더 이상 줄일 수 없으므로 break
            else {
                break;
            }
        }

        // 최종적으로 B == A면 count를, 아니면 -1을 출력
        System.out.println((B == A) ? count : -1);
    }
}

 

업다운 방식으로 푸니 깔끔 그 자체가 되었다 ….

 

 

 

 

 

 

배우게 된 점

입력 값의 범위를 꼼꼼히 살펴볼 것 ! 🐸