[백준] BOJ_9527 - 1의 개수 세기

👀 1. 문제 분석

제약 조건 파악: 입력값 $A$와 $B$의 최대 범위가 무려 $10^{16}$이다. 초기에 생각했던 직관적인 방식, 즉 $A$부터 $B$까지 순회하며 이진수로 변환하고 1의 개수를 조합(nCr)이나 재귀로 세는 방식은 시간 복잡도 $O(B - A)$를 가지므로 무조건 시간 초과(TLE)가 발생한다.

키워드 도출 및 논리적 도약:

1. 구간 합(Prefix Sum): $A$부터 $B$까지의 합을 직접 구하는 대신, 누적합의 성질을 이용해 $f(B) - f(A - 1)$ 형태로 쪼개어 계산하는 것이 핵심이다.
2. 이진수 패턴 찾기: 숫자를 이진수로 나열해 보면 꽉 찬 이진수($2^n - 1$ 꼴)에 포함된 1의 총 개수에는 일정한 규칙이 존재한다.
3. 분할 정복: 임의의 수 $X$에 대한 1의 개수는 '가장 큰 $2^n$ 단위 뭉텅이', '맨 앞자리에 고정된 1의 개수', 그리고 '나머지 꼬리 부분에 대한 재귀 호출'로 나누어 계산할 수 있다.

---

💡 2. 알고리즘 설계

• 사용 알고리즘: 다이나믹 프로그래밍(DP) 기반의 누적합 전처리와 분할 정복(Divide and Conquer)
  
• 자료 구조: $10^{16}$은 이진수로 표현했을 때 약 54자리($2^{54}$)에 해당한다. 따라서 꽉 찬 이진수 구간의 1의 개수를 미리 저장해 둘 크기 55의 1차원 배열 long[] dp를 사용했다.
  
• 시간 복잡도: 최대 54번의 비트 단위 탐색만 거치면 되므로 $O(\log N)$에 수렴한다. 제한 시간 내 통과하기에 매우 넉넉한 속도다.
  

코드 설계 흐름:

1. DP 배열 전처리: 점화식

   $DP[i] = 2 \times DP[i-1] + 2^{i-1}$

   을 사용하여 자리수별 1의 누적 개수를 구한다.

   Java 최적화: Math.pow는 double형 반환으로 인해 정밀도 오차가 발생할 수 있으므로, 빠르고 안전한 비트 시프트 연산자 1L << (i - 1)를 전면 도입했다.

2. 재귀 함수 count(x) 구현:

   • 기저 사례: x <= 0 이면 0 반환.
     
   • x보다 작거나 같은 가장 큰 $2^n$의 지수 n을 찾는다.
     
   • 꼬리 값 계산: diff = $x - 2^n$.
     
   • 반환 수식: dp[n] + (diff + 1) + count(diff)
     

3. 결과 출력: count(B) - count(A - 1) 계산.

---

💻 3. 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static long A, B;
    static long[] dp;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        dp = new long[55]; // 10^16은 대략 2^54이므로 55로 설정
        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());

        // 1. 누적합 DP 전처리 (비트 연산 활용)
        // dp[i] : i비트로 이루어진 모든 이진수(0 ~ 2^i - 1)의 1의 개수 합
        for (int i = 1; i < 55; i++) {
            dp[i] = (dp[i - 1] << 1) + (1L << (i - 1));
        }

        // 2. 구간 합 계산 로직: f(B) - f(A - 1)
        long answer = count(B) - count(A - 1);
        System.out.println(answer);
    }

    // x 이하의 수에 포함된 1의 총 개수를 구하는 분할 정복 메서드
    private static long count(long x) {
        if (x <= 0) return 0; // 기저 사례

        int n = 0;
        // x보다 작거나 같은 가장 큰 2^n의 n(비트 자리수)을 찾음
        while ((1L << (n + 1)) <= x) {
            n++;
        }

        // 2^n을 제외한 나머지 꼬리 부분
        long diff = x - (1L << n);

        // dp[n]: 가장 큰 2^n 뭉텅이의 1의 개수
        // (diff + 1): 맨 앞자리에 1이 고정된 횟수
        // count(diff): 나머지 꼬리 부분에 대한 재귀 탐색
        return dp[n] + (diff + 1) + count(diff);
    }
}

---

✨ 4. 회고 및 배운점

핵심 포인트:

거대한 범위를 다룰 때, 반복문으로 일일이 탐색하는 것을 멈추고 구조적인 패턴을 찾아내야 한다는 점을 뼈저리게 느꼈다. 부분 문제로 쪼개는 식별력이 가장 중요했다.

시행착오 (Troubleshooting):

1. 초기값의 엇갈림: $n=1$일 때의 범위($0 \sim 1$)를 헷갈려 dp[1] = 2로 잘못 초기화하는 실수를 했다. 머릿속으로만 생각하지 않고 직접 숫자를 써보며 기저 사례를 정확히 잡는 것의 중요성을 다시금 배웠다.
2. 값과 개수의 혼동: 배열에 담긴 '1의 총 개수'(dp[i])와 탐색해야 할 '최대 숫자 크기'(B)를 섞어버려 if (B <= dp[i]) break; 와 같은 어처구니없는 오류를 범했다. 변수가 의미하는 바를 주석으로 명확히 남기며 논리를 재조립했다.
3. 수식 누락: $2^n$ 그룹을 나눈 뒤, 최상단 비트의 1이 꼬리 값만큼 반복해서 등장한다는 사실(diff + 1)을 재귀식에서 빼먹는 삽질을 했다. 그림을 그려보고 수식을 다시 완성하며 퍼즐을 맞추는 듯한 짜릿함을 느꼈다.

성장 포인트 🌱

이번 문제를 통해 거대한 숫자($10^{16} \approx 2^{54}$)에 대한 감각을 한층 끌어올릴 수 있었다. 특히 double의 오차 위험성을 피하기 위해 Java의 long 타입과 비트 시프트 연산(1L << n)을 적극 활용하여, 복잡해 보이는 구현을 우아하고 빠르게 최적화하는 기법을 체화한 뜻깊은 시간이었다.