BOJ - 16953 A->B

문제 링크 : https://www.acmicpc.net/problem/16953

문제 유형 : 그리디 알고리즘

문제 풀이 : 핵심 아이디어는 반대로 생각하는 것이다. 즉, A->B가 아닌 B->A로 간다고 생각하자. 

               1) 마지막에서 2로 나누었을 때 나누어 떨어지는 경우엔 나누기 2를 해줌

               2) 일의 자릿수가 1인 경우는 1을 제거

풀이 코드 

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [a,b] = input[0].split(" ").map(Number);
let count = 0;
while(a<=b) {
    if(a===b) {
       console.log(count+1);
       return;
       }
    if(b % 2 === 0) {
        b = b /2;
    } else if(b % 10 === 1) {
         b = b /10;
    } else {
         break;
    }
    count++;
}
if(a!==b) console.log(-1);

 

2) GPTs 해설 

GPT는 BFS의 방법을 알려주었다. 이렇게 풀 수도 있단 것을 유념하면 좋을 것 같다.

문제 설명

• 두 숫자 A와 B가 주어집니다.
• A를 B로 바꾸기 위해 할 수 있는 연산은 다음 두 가지입니다:
  1. A에 2를 곱한다.
  2. A의 가장 오른쪽에 1을 추가한다. (예: A가 2일 때, 21이 됩니다.)
• 최소 연산 횟수를 구해야 합니다. 만약 변환이 불가능하면 -1을 출력합니다.

문제 접근 방법

1. BFS를 이용한 최단 경로 탐색:
   • BFS는 최단 경로를 찾는 데 효과적입니다.
   • 큐를 사용하여 현재 숫자와 연산 횟수를 저장합니다.
   • 큐에서 하나씩 꺼내서 두 가지 연산을 수행한 결과를 큐에 추가합니다.
   • 목표 숫자 B에 도달하면 현재 연산 횟수를 반환합니다.
   • 큐가 비어도 목표 숫자에 도달하지 못하면 -1을 반환합니다.

단계별 문제 풀이

1. 큐 초기화:
   • 큐에 시작 숫자 A와 초기 연산 횟수 1을 저장합니다.
2. BFS 반복:
   • 큐가 빌 때까지 반복합니다.
   • 현재 숫자와 연산 횟수를 큐에서 꺼냅니다.
   • 두 가지 연산을 수행하여 새로운 숫자를 생성합니다.
   • 새로운 숫자가 B와 같다면 현재 연산 횟수를 반환합니다.
   • 새로운 숫자가 B보다 작으면 큐에 추가하고, 연산 횟수를 1 증가시킵니다.
3. 결과 출력:
   • 목표 숫자 B에 도달하지 못하면 -1을 출력합니다

 

코드 설명

1. 입력 처리:
   • 입력값을 받아서 A와 B로 변환합니다.
2. bfs 함수:
   • 큐를 초기화하고 시작 숫자 A와 초기 연산 횟수 1을 저장합니다.
   • 큐가 빌 때까지 반복합니다.
   • 현재 숫자와 연산 횟수를 큐에서 꺼냅니다.
   • 두 가지 연산을 수행하여 새로운 숫자를 생성합니다:
     1. next1 = current * 2
     2. next2 = parseInt(current.toString() + "1")
   • 새로운 숫자가 B와 같으면 현재 연산 횟수를 반환합니다.
   • 새로운 숫자가 B보다 작으면 큐에 추가하고, 연산 횟수를 1 증가시킵니다.
3. 결과 출력:
   • 목표 숫자 B에 도달하지 못하면 -1을 반환합니다.

시간 복잡도

• BFS의 시간 복잡도는 O(N)입니다. 여기서 N은 큐에 삽입되는 노드의 수를 의미합니다.
• 각 숫자에 대해 두 가지 연산을 수행하므로, 최악의 경우 모든 가능한 숫자를 검사해야 할 수 있습니다.

예제 코드 (JavaScript)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ");
const A = parseInt(input[0]);
const B = parseInt(input[1]);

function bfs(A, B) {
    let queue = [[A, 1]];
    while (queue.length > 0) {
        let [current, count] = queue.shift();
        
        if (current === B) return count;
        
        let next1 = current * 2;
        let next2 = parseInt(current.toString() + "1");
        
        if (next1 <= B) queue.push([next1, count + 1]);
        if (next2 <= B) queue.push([next2, count + 1]);
    }
    return -1;
}

console.log(bfs(A, B));