[백준] 16953번 A -> B 문제(Kotlin, 코틀린)

문제

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

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

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

입력

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

출력

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

예제 입력 1 

2 162

예제 출력 1 

5

 

---

 

문제 접근

1.  문제를 해결하기 위해서는 2 -> 162 로 어떻게 가는지 파악하기 보다는 결과인 162 -> 2로 갈 수 있는 방법을 구상하는 것에 도움이 되었다.
2. 만약 마지막 자릿수가 짝수라면 2로 나누고 1이라면 10으로 나누어서 마지막 남은 1을 떨어트리고 원래의 숫자를 찾는 방법인 것이다.

 

알고리즘

1. 각 입력값을 받은 후 b의 1의자리 숫자가 1이라면 10을 나누어 1을 제거한다
2. 짝수라면 2로 나누어서 a에서 2로 곱했을 가능성을 탐색해 나간다.
3. 만약 b가 a보다 작아지거나 짝수가 아니고 1의자릿수가 1이 아니라면 -1을 출력하도록 한다.

정답코드

fun main() {
    val input = readln().split(" ")
    var count = 0
    val a = input.first().toInt()
    var b = input.last().toInt()

    while (a != b) {
        if (a > b) {
            break
        }

        if (b % 10 == 1) {
            b /= 10
            count++
        } else if (b % 2 == 0) {
            b /= 2
            count++
        } else {
            break
        }
    }

    if (a == b) {
        println(count + 1)
    } else {
        println(-1)
    }
}

난이도: 중하

 

헷갈렸던 부분: 만약 b가 a보다 작아지거나 에 해당하는 조건을 생각하지 못해 무한 반복문이 돌아가며 시간초과로 문제에 틀리게 되었다...

 

아쉽게도 1번 틀린 문제이다... 성능체크를 위해 두번 제출하였다.