[Python] 백준 9527번: 1의 개수 세기

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

9527번: 1의 개수 세기

 

import sys
input = sys.stdin.readline


def f(n):
    count = 0

    k = 0
    while 2**k <= n:
        # 0011: p = 4
        p = 2**(k+1)
        p_count = (n+1)//p

        # (완성된 패턴의 갯수) * (패턴의 길이의 절반 = 한 패턴에서 1은 절반이 나오기 때문)
        count += p_count * (p//2)

        # 완성되지 않은 곳의 길이... 0011001에서 left는 3이다.
        left = (n+1) % p
        # 001에서, 00의 길이는 p/2
        count += max(0, left - p//2)

        k += 1

    return count


if __name__ == '__main__':
    A, B = map(int, input().split())

    print(f(B)-f(A-1))

 

 

위 사진처럼 자릿수를 나누어 푼다. 둘째자리(0011으로 시작하는 부분)을 예시로 설명하겠다.

우리는 하나의 패턴(또는 싸이클)을 확인할 수 있다. 0011이라는 패턴이 계속해서 반복하고 있다. k가 1일 때(즉, 둘째자리일 때) 이 패턴의 갯수를 바로 구할 수 있다. p_count = (12+1)//4 = 13//4 = 3으로, 패턴이 3번 나온다는 뜻이다.

그리고 한 패턴의 길이를 2로 나누면 그것이 1이 나오는 갯수가 된다. 즉, 여기선 0011의 길이는 4이고 이것을 2로 나누면 2이다.

이 두 가지 특징을 합쳐서, 특정 자리에서 완성된 패턴들에서의 1의 총 갯수는 p_count * (p/2)가 된다.

 

이제, 패턴이 완성되지 않은 부분에 대해서 고려해야한다. 남은 부분의 길이는 (n+1) % p(변수 left)로 얻을 수 있다. 위 사진에서 마지막 자리(0000000011111)에서는 13을 얻게 된다. 그리고 left - p/2로 1의 갯수를 얻을 수 있다. 지금 고려하고 있는 예시에선, 13 - 8(패턴의 절반) = 5이다. 단, left가 p/2보다 작을 때에는 음수값이 나오게 되므로, max(0, left - p//2)를 통해 식을 완성시켜주었다.