[ 백준 ] 9527 1의 개수 세기

codesver·2023년 3월 23일
0

Baekjoon

목록 보기
41/72
post-thumbnail

Link | 백준 9527번 문제 : 1의 개수 세기

📌 About

문제만 보았을 때는 범위 내의 숫자들를 비트열로 변환하고 1의 개수를 세면 될 것 같다.

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
long from = Long.parseLong(tokenizer.nextToken());
long to = Long.parseLong(tokenizer.nextToken());
LongStream.rangeClosed(from, to).map(i -> Long.toString(i, 2).replaceAll("0", "").length())
		.sum();

하지만 입력값의 범위를 보면 너무 크다는 것을 알 수 있다.

입력값은 1 이상 101610^{16}이다. 즉, 위의 방법으로는 단순 탐색만하는데도 시간초과가 발생한다.

그렇기 때문에 이번 문제는 수학적으로 해결해야 한다.

📌 Solution

숫자들을 비트열로 차례대로 탐색하면 규칙을 확인할 수 있다.

첫 번째 비트는 0101010101...으로 반복된다.

두 번째 비트는 001100110011...으로 반복된다.

세 번째 비트는 0000111100001111...으로 반복된다.

정리하자면 비트의 위치에 따라 반복되는 숫자를 알 수 있고 숫자 N까지의 1 개수를 계산할 수 있다.

계산식은 다음과 같다.

N의 비트열 길이를 L이라 하고 비트의 위치를 오른쪽부터 1이라고 하면,

위치 II의 1 비트 수 NI=(N+1)  /  2I  2I1+(N+1)  %  2I    2I1{N_I = (N + 1) \; / \; 2^I * \; 2^{I-1} + (N + 1) \; \% \; 2^I \; - \; 2^{I-1}} 이다.

1부터 N까지의 1비트 개수는 1LNI\sum^L_1N_I 이다.

주어진 범위가 FROM ~ TO 일 때 (N = TO) - (N = FROM - 1)을 계산하면 된다.

📌 Code

GitHub Repository

public void solve() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    long from = Long.parseLong(tokenizer.nextToken());
    long to = Long.parseLong(tokenizer.nextToken());
    result.append(count(to) - count(from - 1));
}

private long count(long num) {
    long count = 0;
    int len = Long.toString(num, 2).length();
    for (long i = 1; i <= len; i++) {
        long ca = ((num + 1) / (long) Math.pow(2, i)) * (long) Math.pow(2, i - 1);
        long cb = ((num + 1) % (long) Math.pow(2, i)) - (long) Math.pow(2, i - 1);
        count += ca + Math.max(cb, 0);
    }
    return count;
}
profile
Hello, Devs!

0개의 댓글