문제

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

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

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

내 생각

처음에 문제를 봤을때 바로 BFS가 떠올라서 내심 알고리즘 실력이 상승했구나 기뻤다.
하지만, 기쁜 건 순식간에 슬픔으로 됐다. 😅

처음엔 "queue에 A에 연산한 결과들을 넣어두고 B가 될 때까지 반복한다" 라고 로직을 생각했다.

로직이 틀린 것은 아닌데, 문제는 "연산의 최솟값"이지 B가 될 수 있는지에 대한 진위판별이 아니다.

그래서 연산의 결과와 연산 횟수를 담아둘 수 있게 Pair를 queue에 넣고 비교하도록 하여 문제를 해결했다.

깨달은 점

문제를 좀 끝까지 제대로 읽어야 겠다.

아는 거 나왔다고 흥분하지 말고 끝까지 읽어보자

코드

class BOJ16953 {
    fun solve() {
        val (a, b) = readLine()!!.split(' ').map { it.toInt() }
        val queue: Queue<Pair<Long, Long>> = LinkedList()
        var count = 0
        if (a == b) {
            count = 1
        }
        queue.add(Pair(1, a.toLong()))
        while (!queue.isEmpty()) {
            val cursor = queue.poll()
            if (cursor.second == b.toLong()) {
                count = cursor.first.toInt()
                break
            }
            if (cursor.second > b.toLong()) continue
            queue.add(Pair(cursor.first + 1, (cursor.second * 2)))
            queue.add(Pair(cursor.first + 1, (cursor.second * 10 + 1)))
        }
        println(if (count == 0) -1 else count)
    }
}

추가

이 문제 지금 보니까 DP로도 풀 수 있다. DP로 풀어서도 밑에 글을 작성하겠습니다.