<백준> 1의 개수 세기(Gold 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/9527 1의 개수 세기 at main · heesoo-park/ForCodeKata

제출 결과

---

이 문제는 풀었다기보다는 그냥 다른 사람의 풀이를 보고 적었다...

이해가 잘 되지 않더라

딱 비트 수 당 1의 개수를 저장하는 누적합까지는 이해를 했는데 범위에 포함되는 1의 개수를 구하는 쪽의 알고리즘은 영 감을 못 잡았다.

 

뭔가 최대 비트 차례까지 내려가다가 최대 비트가 나오면 거기서 1의 개수를 구한다음 최대 비트를 없애는 방식을 순차적으로 하는 거 같긴 한데 정확하지가 않다.

참 글로 자세히 설명해주시긴 하는데 이게 코드로 옮겨지면서 같은 흐름인지 잘 모른달까..?

 

코틀린으로 문제를 풀 때 비트 연산을 사용하는 건 거의 처음인 거 같다.

log10도 처음 사용해본다.(Double과 Float형 밖에 안 돼서 형변환이 필요했다...)

누적합만이었으면 쉬웠을 텐데 숫자가 엄청 커지고 이진수까지 추가되다보니 많이 어렵게 느껴졌다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*
import java.util.*
import kotlin.math.*

private val acc = LongArray(60)

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    
    acc[0] = 1
    for (i in 1 until 60) {
        acc[i] = (acc[i - 1] shl 1) + (1L shl i)
    }
    
    val (a, b) = br.readLine().split(' ').map { it.toLong() }
    val result = countOne(b) - countOne(a - 1)
    
    print(result)
}

fun countOne(n: Long): Long {
    var num = n
    var cnt = (num and 1)
    val size = (log10(num.toDouble()) / log10(2.0)).toInt()
    
    for (i in size downTo 1) {
        if ((num and (1L shl i)) != 0L) {
            cnt += acc[i - 1] + (num - (1L shl i) + 1)
            num -= (1L shl i)
        }
    }
    
    return cnt
}

 

참고)

https://tussle.tistory.com/1022