[BOJ 9527] 1의 개수 (Java)

BOJ 9527 1의 개수

난이도 : 골드 2

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

9527번: 1의 개수 세기

 

전략

A, B 두 수의 최대 범위가 매우 크므로 무조건 패턴을 찾아서 공식을 만들어야 한다고 접근했다.

1자리 : 0 1 => 1

2자리 : 00 01 10 11 => 4

3자리 : 000 001 010 011 100 101 110 111 => 12

4자리 : 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 => 32

 

여기서 0000 - 1111, 0001 - 1110 이런 식으로 매칭하면 마치 1~s까지 합을 구하는 것처럼 공식을 만들 수 있다.

X자리 이진수들의 1의 합 = X * 2^X / 2 = X * 2^(X-1)

 

그렇다면 임의의 수 A에 대해서 [0, A] 범위에서 1의 개수 합은 어떻게 구할 수 있을까?

A가 [2^3, 2^4) 범위, 즉 4자리 이진수일 때를 가정해보자.

 

이진수에서 MSB(부호 x, 가장 높은 자리의 비트)에 해당하는 자리와 그외의 자리를 분리해보자

A가 13이라면 이진수로는 1101이고

MSB가 0인 부분은 (앞에서 구한 공식을 이용해서) 32/2 = 16이되고 남은 부분을 계산하면 된다.

MSB는 1, 남은 비트는 101 이다.

 

분할정복법으로 4자릿수의 1의 개수를 세는 것과 마찬가지로 3자릿수의 1의 개수 + 101로 바꿀 수 있다.

+ 101인 이유는 MSB가 1이므로 101개 만큼 더해지기 때문이다.

 

좀 더 공식화하면

A가 [ 2^(X-1), 2^X ) 범위에 속하고,

2^(X-1) ~ A까지 범위의 1의 개수를 구하는 함수를 f(A)를 구해보자.

A의 MSB를 b, 남은 비트들을 t라고 하면

f(A) = b * ((X - 1) * 2^(X-2) + t + 1) + f(t) 이다.

 

만약 b가 0이라면 바로 자릿수를 줄여서 다음 재귀호출을 진행한다.

b가 1이라면 1 xxx 이므로

0 xxx에 해당하는 모든 합 = 현재 자릿수 - 1의 모든 비트 1의 합 : (X-1)*2^(X-2)

+

재귀 호출할 xxx 에 포함되지 않은 앞의 1의 개수 : t + 1

 

설명은 어렵게 했지만 코드는 생각보다 깔끔하다.

분할정복을 위처럼 재귀적으로 구현할 수 있으며, 전체적인 시간복잡도는 O(logN)이 된다.

B와 A-1의 1의 개수를 구했다면 두 개의 차를 구하면 정답이 된다.

 

시행착오

식을 유도하는 과정들에서 시행착오가 있었으며, 이후 구현에서는 없었다.

 

코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A, B;
        A = sc.nextLong();
        B = sc.nextLong();
        System.out.println(getOnes(B, binLength(B)) - getOnes(--A, binLength(A > 0 ? A : 1)));
    }

    static long getOnes(long num, int x) {
        if (x == 1) return num == 1 ? 1 : 0;

        long msb = (1L << x - 1) & num;
        long t = num - msb;
        long b = num >> (x - 1);

        return b * ((x - 1) * (1L << x - 2) + t + 1) + getOnes(t, x - 1);
    }

    static int binLength(long n) {
        int result = 0;
        while (n > 0) {
            n >>= 1;
            result++;
        }
        return result;
    }
}

 

깨달은 점

A, B의 범위가 힌트인 문제였다.

처음에는 log 시간복잡도로 간단하게 만들 수 있을 줄 알았는데

패턴들을 생각하며 공식을 만드는 과정이 은근히 오래걸렸다.