[백준 16953번] [Kotlin] A → B

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

16953번: A → B

 

난이도 : 실버 2
태그 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 너비 우선 탐색

 

 

설명

A가 주어지면

1. 2를 곱한다

2. 오른쪽에 1을 추가한다

두가지 연산을 사용해 가장 적은 연산횟수로 B로 만드는 문제입니다

 

다이나믹 프로그래밍, 그리디 알고리즘, BFS 등 여러 알고리즘을 사용해 풀이할 수 있으며,

저는 그리디 알고리즘을 사용해 풀이하였습니다.

 

A -> B 보단, B를 역으로 A로 만드는 과정이 더 쉬우며,

오른쪽에 1을 추가하는 연산은 10으로 나눴을때 나머지가 1이면 오른쪽에 1을 추가한 연산으로,

2로 나눴을때 나머지가 0이면, 2를 곱한 연산으로 역추적하며 B에서 A를 찾아갑니다.

 

 

소스코드

fun main() {
    val ab = readLine()!!.split(" ")
    val a = ab[0].toInt()
    var b = ab[1].toInt()

    var cnt = 0

    while (a != b) {
        if (a > b) {
            println(-1)
            return
        }

        // 10으로 나눴을때 나머지가 1 --> 오른쪽에 1 삽입
        if (b % 10 == 1) {
            b /= 10
        } else if (b % 2 == 0) {
            // 10으로 나눌 수 없으면 2로 나눔
            b /= 2
        } else {
            println(-1)
            return
        }
        cnt++
    }

    println(cnt + 1)
}

 

후기

기존의 백준에서 푼 문제들을 올리고 있는데,

꽤 재밌게 풀었던 문제였던게 기억나네요.