백준 - 1094 막대기(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/1094

 

[문제 설명]

막대기를 쪼개서 x를 만드려면 최소 몇개의 막대기가 필요할까?

 

[접근 방법]

방법 1 : 최소큐를 이용하여 로직을 구현하기.

주어진 조건대로 따라서 구현하면 된다.

최소 길이인 막대기를 매번 선형 탐색하면 시간이 길어지므로(O(N)), 최소큐(O(logN))를 사용하여 탐색한다.

 

방법 2 : 1인 비트의  개수를 세어 준다.

문제를 보다 보면 비트의 개수를 세면 된다.

직접 구현해줘도 되지만 1인 비트의 개수를 세주는 메소드가 있으므로 그걸 사용했다.

 

[방법 1]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.PriorityQueue

fun main() {
    // 1번 방법 : 구현
    val br = BufferedReader(InputStreamReader(System.`in`))
    var currentLength = 64
    // 1 <= x <= 64
    val x = br.readLine().toInt()

    if (x == currentLength) {
        println(1)
        return
    }

    val minQueue = PriorityQueue<Int>()
    minQueue.offer(currentLength)

    while (minQueue.isNotEmpty()) {
        // 가장 짧은 스틱
        val minLenStick = minQueue.poll()
        if (currentLength - minLenStick / 2 > x) {
            currentLength -= minLenStick / 2
            minQueue.offer(minLenStick / 2)
        } else if (currentLength - minLenStick / 2 == x) {
            currentLength -= minLenStick / 2
            println(minQueue.size + 1)
            return
        } else {
            minQueue.offer(minLenStick / 2)
            minQueue.offer(minLenStick / 2)
        }
    }
}

[방법 2]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    // 1 <= x <= 64
    println(BufferedReader(InputStreamReader(System.`in`)).readLine().toInt().countOneBits())
}