백준 16953번: A → B

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

문제 풀이

그리디

count = 역으로 연산을 한 횟수 + 1

num = B에서부터 역으로 연산을 하는 동안의 수

num이 0보다 클 동안 다음 단계를 반복함

1. num이 A와 같다면 반복문 탈출

2. num의 끝자리가 1이면 num에 10으로 나눈 몫 대입

3. num이 짝수라면 num을 2로 나눔

4. 둘 다 아니라면 count에 -1을 대입하고 반복문 탈출

이 단계를 거쳐서 반복문을 탈출하면 num이 0이거나 A거나 연산의 결과가 아닐 수 있음

연산의 결과가 아니라면 이미 count가 -1이므로 더 이상 바꿀 필요가 없음

num이 A라면 출력해야 하는 값이 이미 count에 저장되어 있음

num이 0이라면 B가 연산의 결과긴 하지만 A를 연산해서 B를 만들 수는 없으므로 count에 -1을 대입해주어야 함

이러면 count에 최소 연산 횟수 + 1이나 -1이 저장되어 있으므로 count를 출력하면 정답

풀이 설명

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

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

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

첫 번째 연산의 결과는 항상 짝수이고, 두 번째 연산의 결과는 항상 끝의 자리가 1이 된다. 그러므로 연산된 수가 짝수라면 첫 번째 연산을 한 것이고 끝의 자리가 1이라면 두 번째 연산을 한 것이다.

즉, 현재 수의 상태에 따라 연산을 역으로 추적할 수 있다는 뜻이다. 그러므로 B에서부터 연산을 역으로 실행해서 A를 만들 수 있는지 확인하면 되는 문제다. 따라서 B가 짝수라면 2로 나누고, 끝의 자리가 1이라면 10으로 나눈 몫을 대입하면 된다.

이렇게 역으로 연산을 해서 B를 A로 만들 수 있다면 연산을 통해 A를 B로 만들 수 있다는 뜻이므로 B를 한 단계씩 역으로 연산해서 A가 되는데 연산을 몇번 하면 되는지 확인하면 된다.

출력에서 최소 횟수에 1을 더한 값을 출력하라고 했으니 최소 횟수를 저장하는 count의 초기값을 1로 설정하면 된다. 그 이후에 B를 역연산할때마다 count를 1씩 증가시키면 된다.

그러나 B를 역연산해서 A가 나오지 않을 수 있다. 역연산의 결과로 0이 되거나 끝자리가 1이 아닌 홀수가 되면 역연산이 더이상 불가능한 것이므로 이 때는 count에 불가능하다는 의미의 -1을 대입한다.

이렇게 구한 count를 출력해주면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val A = nextInt()
    val B = nextInt()
    var count = 1
    var num = B
    while(num > 0){
        if(num == A){
            break
        }
        if(num % 10 == 1){
            num /= 10
        } else if(num % 2 == 0){
            num /= 2
        } else {
            count = -1
            break
        }
        count++
    }
    if(num == 0) count = -1
    println(count)
}