[백준/BOJ] 12931번: 두 배 더하기

문제

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

12931번: 두 배 더하기

해설

배열 A를 B로 만들 수도 있겠지만, 좀 더 쉽게 생각해보면 배열 B를 모두 0의 값을 가지게 만들어도 된다.

문제를 보면,

1. 배열에 있는 값 하나를 1 증가시킨다.
2. 배열에 있는 모든 값을 두 배 시킨다.

이를 반대로 생각하면 다음과 같다.

1. 배열에 있는 값 하나를 1 감소시킨다.
2. 배열에 있는 모든 값을 2로 나눈다.

여기서, 2번을 실행시키기 위해서는 모든 값이 짝수여야한다.

 

따라서 과정을 보면,

1. 배열의 요소 중 홀수인 요소를 -1해준다.
2. 모든 요소가 짝수라면 /2를 해준다.

이처럼 되는 것을 확인할 수 있다.

즉, 그리디 알고리즘을 통해 문제를 해결할 수 있다.

홀수를 짝수로 만들고 그 값들을 /2한다.

이러한 최적화 과정을 거치면서 해결을 하게 된다.

소스 코드

import java.util.*

private var n = 0
private lateinit var arr: IntArray

fun main() {
    input()
    println(solve())
}

private fun input() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    arr = IntArray(n)
    val st = StringTokenizer(readLine())

    repeat(n) { i -> arr[i] = st.nextToken().toInt() }
}

private fun solve(): Int {
    var cnt = 0

    while(true) {
        repeat(n) { i ->
            if(arr[i] % 2 == 1) {
                arr[i]--
                cnt++
            }
        }

        if(!allZero()) {
            repeat(n) { i -> arr[i] /= 2 }
            cnt++
        }

        if(allZero()) break
    }
    return cnt
}

private fun allZero(): Boolean {
    repeat(n) { i ->
        if(arr[i] != 0) return false
    }
    return true
}