[백준][코틀린] 16953 A → B

문제 내용

문제

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

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

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

입력

첫째 줄에 A, B (1 ≤ A < B ≤ \(10^9\))가 주어진다.

출력

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

예제 입력	예제 출력
2 162	5
4 42	-1
100 40021	5

문제 풀이

재귀를 이용해 문제를 풀었다. 숫자에다 문제 조건대로 연산을 수행하는데, 마이너스 연산이나 나누기 연산처럼 값이 줄어드는 경우는 없으므로 계산 값이 b를 넘어서지 않는 경우만 재귀를 호출하였다.

이때, 인자가 b와 값이 같을때, cnt의 값과 minimum 값과 비교하여 작은 값을 minimum에 저장시킨다. 

재귀가 끝나고 나면, 만약 minimum 값이 초깃값 (Long.MAX_VALUE)와 같다면, -1을 출력하고 그렇지 않다면 최솟값에 1을 더해서 출력한다. 

</>̆̈ 코드

import java.util.*

// A -> B

private var a = 0L; private var b = 0L
private var minimum = Long.MAX_VALUE

fun main() {
    StringTokenizer(System.`in`.bufferedReader().readLine()).run {
        a = nextToken().toLong(); b = nextToken().toLong()
    }
    changeNumber()
    print(if (minimum == Long.MAX_VALUE) -1 else minimum + 1)
}

private fun changeNumber(number: Long = a, cnt: Long = 0L) {
    if (number == b) {
        minimum = minOf(minimum, cnt); return
    }
    if (number * 2 <= b) changeNumber(number * 2, cnt + 1)
    if (number * 10 + 1 <= b) changeNumber(number * 10 + 1, cnt + 1)
}

링크

16953번: A → B