김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 9527 1의 개수 세기 파이썬(Python)

문제 링크

수열의 규칙성을 찾고 점화식을 활용하는 문제.
A에서 B 사이 1의 개수는 결국 1부터 B까지의 1의 개수에서 1부터 A-1까지의 1의 개수를 뺀 값이다.
1부터 임의의 수까지의 1의 개수를 구하기 위해 get_cum_sum()함수를 사용했다.
숫자의 자리수가 늘어날 때마다, 이전의 수열이 2번 반복되는 모양이 나타난다(한번은 1이 앞에, 한번은 0이 앞에).
따라서, 자리수를 기준으로 숫자들을 자르고, 각 합들을 계산하면 규칙성을 찾을 수 있고, 그 규칙은 n[k] = 2 * n[k-1] + 2 ** k이다.
이 점화식을 풀면 2 ** (k - 1) * (k + 2)이다.
이제, 2의 제곱수보다 1 작은 수는 위 수열의 합 2 ** k * (1 + k)로 한번에 구할 수 있다.
그 이후 남은 수는 이진수의 규칙성을 활용해 재귀적으로 나누어주면서 계산하면 된다.
또한, 제곱수 부분을 구할 때 주의할 점이 있는데, math.log2() 함수는 부동소수점 문제 상 매우 큰 수에 대해 부정확한 결과를 내놓는다.
따라서, len(bin()) - 3을 이용해서 이진수의 길이를 추출하는 방법을 사용했다.

#!python

a, b = map(int, input().split())

# 1부터 n까지의 누적 1의 개수를 구하는 함수
def get_cum_sum(n):
    k = len(bin(n + 1)) - 4
    sum_under_exp = int(2 ** k * (1 + k))    # 2의 제곱수까지의 1의 개수(수열의 합)
    over = n + 1 - 2 ** (k + 1)
    sum_over_exp = get_mid_sum(over, k + 1)  # 나머지 숫자들의 1의 개수
    return sum_under_exp + sum_over_exp

# 1번째부터 n번째 k+1자리 이진수까지의 1의 개수를 구하는 함수
def get_mid_sum(n, k):
    if not n:
        return 0
    if not k:
        return 1
    if n >= 2 ** (k - 1):
        m = k - 1
        mid = int(2 ** (m - 1) * (m + 2))            # 수열의 일반항
        over = n - 2 ** m
        return mid + over + get_mid_sum(over, k - 1)
    return get_mid_sum(n, k - 1)

print(get_cum_sum(b) - get_cum_sum(a - 1))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑