[Kotlin] 백준 12931 : 두 배 더하기

문제 링크

12931번: 두 배 더하기

---

문제 해설

문제는 모든 값이 0으로 채워진 배열을 입력으로 주어진 배열로 만드는 것이지만, 역으로 생각해보면 입력으로 주어진 배열의 모든 값을 0으로 만들기 위한 연산의 최소 횟수를 구하는 문제라는 것을 알 수 있다.

 

역으로 접근하면 된다는 것을 알았으니 어떻게 연산을 진행할 지 생각해보자. 배열의 모든 값을 반으로 나누는 것이 값 하나를 1 감소시키는 것보다 훨씬 효율적이다. 그런데 홀수는 반으로 나눌 수 없으니 1 감소시켜야 한다. 즉, 배열의 모든 값이 0이 될 때까지 아래의 연산을 계속 반복하면 된다.

1. 배열의 모든 홀수를 1만큼 감소시키고 그 횟수만큼 연산 횟수를 증가시킨다.
2. 배열의 모든 값이 0이면 반복문을 종료한다.
3. 배열의 모든 값을 2로 나누고 연산 횟수를 1 증가시킨다.

여기서 반복문을 종료하기 위한 검증 단계가 배열의 값을 1 감소시키는 연산과 모든 값을 2로 나누는 연산 사이에 들어가게 되는데, 나누기 연산의 값이 0인 경우는 0을 나누는 경우밖에 없기 때문이다.

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val array = StringTokenizer(readLine()).run { IntArray(n) { nextToken().toInt() } }
    var count = 0
    while (true) {
        for (i in array.indices) {
            if (array[i] % 2 == 1) {
                count++
                array[i]--
            }
        }

        if (array.count { it != 0 } == 0) break

        for (i in array.indices) {
            array[i] /= 2
        }
        count++
    }
    println(count)
}