백준9527: 1의 개수 세기(Java, Python)

오랜만에 풀이가 야무진 문제를 풀어서 블로그에 남긴다.

인덱스랑 비트, 제곱근 등등 이것저것 수식 생각하느라 머리아팠던 문제

일단 입력값의 범위가 매우 크다.
1~10^16
일반적인 순회로는 못푼다 -> 숫자를 2의 거듭제곱 단위로 나누어서 생각하자
우선 최댓값의 범위가 10^16이니, 최댓값보다 작은 가장 큰 2의 거듭제곱을 구한다.
아래와 같은 수식으로 구할 수 있고, 따라서 시간/공간복잡도 또한 53이 된다
`log2(10^16) = 53.15`
그래서 배열의 인덱스를 53보다 조금 넉넉하게 60으로 잡음

풀이과정을 풀어서 설명하면 다음과 같다
1. N자리수의 1의 개수의 합을 구한다
  - ex: 세 자리수의 1의 개수의 합을 구한다(`100`, `101`, `110`, `111`)
  - 이는 두 자리수로 구할 수 있는 조합에다가 맨 앞에 1을 붙인 값과 마찬가지이다.
  - 즉, 이전까지의 누적합에 현재 숫자의 개수를 구하면 된다.
  - 현재 숫자의 개수는 어떻게 구하냐 ? -> 2의 거듭제곱 단위로 증가하기때문에, `2^(구해야 할 자리수-1)`개가 더해야 할 숫자 개수가 된다.
위의 과정을 통해 `dp`배열과 `sum`배열값을 구할 수 있다.
```
        dp = new long[60]; // 2^(i-1) ~ 2^i 까지의 1의개수의 합(그 자리수의 누적합)
        sum = new long[60]; // 0~2^i - 1 까지의 1의개수의 합 (0부터의 전체 누적합)
```

그러면 이제 `2^n - 1`에 대한 누적합값은 배열에 저장되어있다.
그러면 6이나 13같이 나머지가 생기는 숫자들은 어떻게 구하냐 ?
위의 논리와 같은 논리인데, 이젠 거꾸로 계산하면 된다.
6을 예시로 들면
1. 6의 누적합값을 구한다
2. 0~3의 누적합 값은 sum[2]값을 그대로 읽으면 된다
3. 그러면 남은 수가 456이 된다.
4. 4,5,6의 합 = 0,1,2의 합 + 3
  - 왜냐? 비트로 환산하면 0=00, 1=01, 2=10인데 여기에 비트 맨 앞에 값을 붙여주면 4(100),5(101),6(11)이 된다.
  - 즉, 구해야 할 수보다 작은 수 중에서 가장 큰 2의 거듭제곱값을 뺀 상태에서 다시 구해주면 된다.
  - 3은 왜 더하냐 ? 숫자가 총 세 개가 남기 때문. 비트를 하나 감소시킨 상태의 값을 recur로 구할거기때문에, 붙어야 할 비트값을 미리 더해준다.
5. 그럼 다시 0,1,2의 합을 구한다
6. 0~1의 누적합 값은 sum[1]값을 그대로 읽으면 된다
7. 그러면 남은 수가 2가 된다.
8. (4)와 같은 원리로, 2의 합 = 0까지의 누적합 + 1

생각할게 많고 재밌는 문제였다.

 

파이썬 풀이

A, B = map(int, input().split())

dp = [0] * 60
sum = [0] * 60

dp[1] = 1
sum[1] = 1

for i in range(2, 60):
    dp[i] = sum[i-1] + pow(2, i-1)
    sum[i] = sum[i-1] + dp[i]

def recur(num, exp):
    if num == 0: return 0
    if num == 1: return 1

    next = num - (1 << (exp-1))
    if next == 0:
        return sum[exp-1] + 1
    else:
        return sum[exp-1] + recur(next, next.bit_length()) + next + 1

print(recur(B, B.bit_length()) - recur(A-1, (A-1).bit_length()))

 

자바 풀이

import java.util.*;

public class Main {
    private static long[] sum;

    public static void main(String[] args) {
        long[] dp = new long[60]; // 2^(i-1) ~ 2^i 까지의 1의개수의 함
        sum = new long[60]; // 0~2^i - 1 까지의 1의개수의 합 (누적합)
        dp[1] = 1;
        sum[1] = 1;

        for (int i = 2; i < dp.length; i++) {
            dp[i] = sum[i - 1] + (long) Math.pow(2, i - 1);
            sum[i] = sum[i - 1] + dp[i];
        }

        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong() - 1;
        long B = sc.nextLong();
        System.out.println(recur(B, getExp(B)) - recur(A, getExp(A)));
    }

    private static int getExp(long num) {
        return 64 - Long.numberOfLeadingZeros(num);
    }

    private static long recur(long num, int exp) {
        if (num == 0) return 0;
        if (num == 1) return 1;
        long next = num - (1L << (exp - 1));
        if (next == 0)
            return sum[exp - 1] + 1;
        else
            return sum[exp - 1] + recur(next, getExp(next)) + next + 1;
    }
}