[Kotlin] 백준 17830 : 이진수씨의 하루 일과

문제 링크

17830번: 이진수씨의 하루 일과

---

문제 해설

주어진 조건에 따라 이진수의 곱셈을 수행했을 때의 최대 자릿수와 최소 자릿수를 구해야한다. 그런데 이진수의 곱셈이라고는 하지만 실제로 곱셈을 수행하게 되면 최대값이 \(2^{2,000,000}\)이 되기 때문에 실제 곱셈을 수행할 수 없다. 설령 BigInteger를 사용하여 계산한다고 해도 값이 너무 크기 때문에 시간초과가 발생한다.

 

우선 오늘의 이진수를 최대 자릿수로 만들기 위해선 ?가 모두 1이면 된다. 반대로 오늘의 이진수를 최소 자릿수로 만들기 위해선 ?가 모두 0이면 된다.

 

이 문제를 풀기 위해서는 2진수의 특성을 이용해야 한다. 2진수의 각 자릿수는 \(2^n\)이기 때문에 여기에 \(2^m\)을 곱하면 전체 자릿수는 \(n+m+1\)이 된다. 예를 들면 \(1111 \times 1000=1111000\)이 되는 식이다. 따라서, 기본적으로 두 이진수를 곱한 자릿수는 leading zero를 제외한 자릿수의 합계 - 1이 된다.

 

다음은 두가지 경우를 생각해봐야 한다. \(B\)에 1이 여러개 있는 경우와 하나도 없는 경우이다. \(B\)에 1이 하나도 없는 경우는 \(B=0\)인 경우, 즉 곱한 결과값이 0이 되므로 무조건 자릿수가 1이 된다. 반대로 \(B\)에 1이 여러개 있는 경우라면 \(A\)의 모든 비트가 1이기 때문에 leading zero를 제외한 자릿수의 합계가 된다. 이 경우의 예로는 \(1111\times 1??1\)를 들 수 있다. 이 경우는 결과값이 \(1111000\)에 \(111100\), \(11110\), \(1111\) 중 하나 이상을 더한 것이 되는데 셋 중 어느것을 더하더라도 자릿수는 1만 증가하게 된다.

 

자릿수를 구하는 방법을 알았으니 이제 계산만 하면 된다. 최대 자릿수를 구할 때는 1과 ? 중에 자릿수가 더 큰 경우(= 주어진 \(B\)의 문자열에서 1과 ?의 인덱스 중 더 작은 값)을 기준으로 1과 ?의 개수의 합을 기준으로 하여 분기처리를 하면 된다. 최소 자릿수를 구할 때는 ?를 무시하고 1의 개수를 기준으로 하여 분기처리를 하면 된다.

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    repeat(readLine().toInt()) {
        val st = StringTokenizer(readLine())
        val n = st.nextToken().toInt()
        val bin = st.nextToken()
        val indexOfQ = bin.indexOf('?')
        val indexOf1 = bin.indexOf('1')
        var countQ = 0
        var count1 = 0
        for (c in bin) {
            when (c) {
                '1' -> count1++
                '?' -> countQ++
            }
        }
        val max = if (indexOfQ < 0 || indexOf1 < 0) n + (bin.length - maxOf(indexOfQ, indexOf1)) else n + (bin.length - minOf(indexOfQ, indexOf1))
        val min = n + (bin.length - indexOf1)
        bw.write(if (count1 + countQ == 0) "1 " else if (count1 + countQ == 1) "${max - 1} " else "$max ")
        bw.write(if (count1 == 0) "1\n" else if (count1 == 1) "${min - 1}\n" else "$min\n")
    }
    bw.close()
}