[Kotlin] 백준 25418 : 정수 a를 k로 만들기

문제 링크 : https://www.acmicpc.net/problem/25418

문제 해설

정수 \(A\)에 1을 더하거나 2를 곱하는 연산을 반복하여 정수 \(K\)를 만들 때 필요한 가장 적은 연산 횟수를 구해야 한다.

 

역으로 생각해보면 이 횟수는 \(K\)를 2로 나누거나 1을 빼는 연산을 반복하여 \(A\)를 만드는 횟수와 동일하다.

 

2로 나누는 연산이 1을 빼는 연산보다 훨씬 효율적이기 때문에 \(K\)를 \(A\)로 만들 때 까지 현재 수가 짝수라면 2로 나누고, 홀수라면 1을 빼주면 된다.

while (current != a) {
    if (current and 1 == 0) {
        current /= 2
    } else {
        current--
    }
    count++
}

다만 한가지 생각해야할 점이 있다.

 

만들어야 하는 수가 \(A\)라고 명시되어 있기 때문에 \(K\)가 짝수라고 무작정 나눌 수는 없다. 예제 2의 경우를 보자.

여기서 8을 2로 나눠버리면 4가 되어버리기 때문에 영영 \(A\)가 될 수 없다. 이 경우를 방지하기 위해 \(K\)를 2로 나누는 조건에 현재 \(K\)를 2로 나눈 수가 \(A\) 이상이라는 조건을 걸어줘야 한다.

while (current != a) {
    if (current and 1 == 0 && current / 2 >= a) {
        current /= 2
    } else {
        current--
    }
    count++
}

Code

fun main() = with(System.`in`.bufferedReader()) {
    val (a, k) = readLine().split(' ').map { it.toInt() }
    var count = 0
    var current = k
    while (current != a) {
        if (current and 1 == 0 && current / 2 >= a) {
            current /= 2
        } else {
            current--
        }
        count++
    }
    println(count)
}

유사한 문제

• [Kotlin] 백준 12931 : 두 배 더하기 : 연산 방법이 비슷하지만 배열 전체에 행하는 연산이고, 초기 값이 고정되어 있다.