[백준] 9527 - 1의 개수 세기(Counting ones) (G2)

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

9527번: 1의 개수 세기

class5 문제를 풀면서 만났던 생 수학 문제.

 

두 정수가 주어질 때, 두 정수를 포함하는 범위의 모든 정수를 이진수로 변환했을 경우

1의 개수를 모두 세는 문제이다.

 

곧이곧대로 구하면 수의 범위가 커서 시간초과를 받는다.

나는 다음과 같은 풀이를 떠올렸다.

 

1. 누적합

[a, b] 구간의 모든 정수의 이진수의 1의 개수를 직접 구하기보다

[1, a] 구간의 이진수의 1의 개수를 구하고

[1, b] 구간의 이진수의 1의 개수를 구한다음

 

[1, b] 구간의 답 - [1, a] 구간의 답 + a의 이진수의 1의 개수

 

를 해서 답을 구하도록 하는 누적합 풀이를 우선 떠올렸다.

 

이걸 코드로 구현하면 아래와 같다.

a, b = map(lambda x: str(bin(int(x)))[2:], input().split())
print(Count(b) - (Count(a) - a.count('1')))

이제 어떻게 [1, x] 구간의 1의 개수를 셀지, 즉, 저 Count 함수에 대한 구현을 고민할 차례다.

 

2. [1, x] 구간의 답을 구하는 방법?

이 부분을 빠르게 계산하기 위해 고민을 했다.

그래서 일단 문제 예시에 나온 2부터 12까지의 수를 전부 노트에 적고,

2진수로 바꾼다음 직접 1의 개수를 세보았다.

 

그렇게 한가지 규칙을 찾을 수 있었다.

 

10110 이라는 이진수의 1부터 모든 1의 개수는

10110 보다 작은 이진수에 대해 1을 채우는 경우의 수를 찾는 것과 같다.

 

10110 의 경우

1010_ 은 반드시 10110 보다 작고

100_ _ 도 반드시 10110보다 작고

0_ _ _ _ 도 반드시 10110 보다 작다

 

(이때, 10_ _ _ 은 고려하지 않는다.

10_ _ _ 은 10111 이라는 10110보다 큰 경우의 수를 가질 수 있기 때문이다.)

 

그리고 1010_, 100_ _, 0_ _ _ _ 은 서로 겹치지 않는다.

따라서 이 각각의 경우에 대해 1의 개수를 세서 합쳐주면 된다.

 

이걸 일반화 하면, 어떤 이진수에 대해

오른쪽에서부터 순회하면서, 1을 만나면 해당 1을 0으로 바꾸고 그 오른쪽의 모든 자리를 빈칸으로 만들었을 때,

해당 빈칸에 값을 채워서 얻을 수 있는 1의 개수의 합이 "해당 1이 0으로 바뀌었을 때의 1의 개수 합" 이다.

이걸 1을 만날 때마다 0으로 바꿔준다고 생각하고 경우의 수를 세서 합치면

우리가 원하는 [1, x] 구간의 1의 개수합을 얻을 수 있다.

 

이때 빈칸의 개수가 n 개이면 해당 n개에 대해 모든 1의 개수의 합은

n 개중 r 개를 1로 채우는 경우의 수에 r 을 곱하는 것을, r에 대해 1부터 n 까지 반복하면 된다.

 

 

보기좋게 수식으로 정리하면 다음과 같다.

PrefixCount 는 100_ _ 처럼 앞에서 고정해둔 부분의 1의 개수이다.

 

이 부분을 코드로 작성한 것이 아래와 같다.

 

def Calculate(n, default_one_count):
    value = default_one_count
    for r in range(1, n+1):
        value += (r + default_one_count) * nCr(n, r)

    return value

여기에서 관건이 바로 nCr 을 빠르게 계산하는 것이다.

제일 큰 수인 10e16 을 이진수로 나타내면 길이가 54자이다.

즉 최악의 경우 54C27 의 경우의 수를 계산해야 하는 것이다.

 

이런 계산을 빠르게 하기 위해 인터넷의 검색으로 조합을 계산하는 함수를 찾았다.

def nCr(n, r):
    if n < 1 or r < 0 or n < r:
        raise ValueError
    r = min(r, n-r)
    numerator = reduce(op.mul, range(n, n-r, -1), 1)
    denominator = reduce(op.mul, range(1, r+1), 1)
    return numerator // denominator
    
    # 출처 : https://brownbears.tistory.com/459

그냥 무식하게 combinations 모듈을 이용해서 리스트화 시키고 길이 구하면 시간이 오래 걸린다.

---

이걸로 각 구간에 대해 개수도 구하는 방법을 찾았으니 위에서 작성한 코드를 합쳐주면 끝이다.

 

from functools import reduce
import operator as op

def nCr(n, r):
    if n < 1 or r < 0 or n < r:
        raise ValueError
    r = min(r, n-r)
    numerator = reduce(op.mul, range(n, n-r, -1), 1)
    denominator = reduce(op.mul, range(1, r+1), 1)
    return numerator // denominator

def Calculate(n, default_one_count):
    value = default_one_count
    for r in range(1, n+1):
        value += (r + default_one_count) * nCr(n, r)

    return value


def Count(binary):
    whole_one_count = binary.count('1')
    size = len(binary)
    answer = whole_one_count
    for i in range(size):
        if binary[size-1-i] == '0':
            continue
        whole_one_count -= 1
        answer += Calculate(i, whole_one_count)

    return answer

a, b = map(lambda x: str(bin(int(x)))[2:], input().split())
print(Count(b) - (Count(a) - a.count('1')))