[백준][자바스크립트] 16953번_A → B

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

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

100 → 200 → 2001 → 4002 → 40021

---

문제 풀이

정방향(A → B)으로 접근시, A=2, B=162일 때 2 → 4 → 8 → 81 → 162와 같이 여러 경로가 존재할 수 있지만, 모든 경로를 탐색하는 것은 비효율적이다.

하지만 역방향(B → A)으로 접근하게 된다면 각 단계에서 할 수 있는 선택이 항상 정해져 있다.

1) 값이 2로 나누어 떨어지는 경우 → 2로 나누는 연산만 사용 가능하다.
2) 그렇지 않고, 일의 자릿수가 1인 경우 → 1을 빼고 10으로 나누는 연산만 사용 가능하다.
3) 위 경우가 모두 해당되지 않는 경우 → 더 이상 이동이 불가능하므로, 종료한다.

이것 외의 다른 경우의 수가 아예 존재하지 않는 것을 알 수 있다.
각 상황에서 이동 경로는 단 하나만 존재하므로, 그리디 알고리즘에 해당한다.

소스코드

수도 코드

시작:
    A와 B 입력 받기
    연산 횟수 cnt = 0

    while B > A:
        if B가 짝수면:
            B = B // 2
            cnt += 1
        elif B의 마지막 자리가 1이면:
            B = (B - 1) // 10
            cnt += 1
        else:
            break

    if B == A:
        cnt + 1 출력
    else:
        -1 출력

코드 구현

const fs = require('fs');
const [A, B] = fs.readFileSync('input.txt').toString().trim().split(' ').map(Number);

function changeNum(a, b) {
    let cnt = 0;
    while (b > a) {
        if (b % 2 === 0) {
            b = Math.floor(b / 2);
            cnt++;
        } else if (b % 10 === 1) {
            b = Math.floor((b - 1) / 10);
            cnt++;
        } else {
            break;
        }
    }
    return b === a ? cnt + 1 : -1;
}

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

JavaScript는 / 연산 시 실수를 반환하므로 Math.floor()로 정수화해야 한다.

만약 Math.floor()를 사용하지 않고 그냥 /만 쓴다면, 결과가 소수일 수 있기 때문에 '정수 연산'에 오류가 발생할 수 있다.

정수 몫, 내림 연산, 소수점 버림이 필요할 때 Math.floor()를 사용합니다.
JavaScript의 / 연산 결과가 실수이기 때문입니다.
반복문, 인덱스, 정수 연산 등에서 안전하게 정수값을 얻을 수 있습니다.