문제 링크

성능 요약

메모리: 14260 KB, 시간: 100 ms

분류

비트마스킹, 수학, 누적 합

제출 일자

2025년 1월 22일 17:40:11

문제 설명

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.

즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

 

입력

첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 1016)

출력

1의 개수를 세어 출력한다.

풀이

느낀점

• 시그마의 의미를 10년 가까이 완전히 까먹고 있었다가 이 문제를 풀고 다시 머리에 입력이 됐다. 그냥 문제를 글로 읽은 내용과 같다.
• 규칙이 있다는건 알겠는데, 숫자의 크기가 커서 쌩으로 누적합을 하면 분명 시간초과였다.
• 모르겠어서 다른 풀이를 참고했다. 그림을 직접 그려보면 이해가 잘 된다.

설계 : 60분

• 1부터 숫자들의 이진법 표기를 나열하면 규칙이 있다. 2진수의 길이가 1 늘어날때마다(즉, 2의 거듭제곱마다) 왼쪽에 1만 더해지고 처음부터 누적 나열된 뭉텅이가 반복된다.
• 이 규칙을 사용해 2의 각 거듭제곱까지의 이진수 1개수 누적합을 배열로 저장한다.
  • dp[i] = ((long) Math.pow(2, i)) + (dp[i-1] * 2)
• 배열에는 2의 거듭제곱 값에 대한 1의 개수만 저장 되어 있다. 따라서 그 사이의 수들은 바로 알 수 없다.
• 하지만 1번으로 언급한 규칙을 사용하면 목표한 수를 비트마스킹으로 역순회하며 dp에 저장된 값들을 더해 빠르게 구할 수 있다.
  
  

코드(Java)

• 구현 시간: 50분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 1의 개수 세기_9527
 * Date: 2025.01.22
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static long[] dp;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        init();

        String[] input = br.readLine().split(" ");
        long A = Long.parseLong(input[0]);
        long B = Long.parseLong(input[1]);

        long fx_A = getOne(A - 1);
        long fx_B = getOne(B);

        bw.write(String.valueOf(fx_B - fx_A));
		bw.flush();
		bw.close();
		br.close();
	}

    private static void init()
    {
        dp = new long[56];
        dp[0] = 1;
        for (int i = 1; i < 56; i++) dp[i] = ((long) Math.pow(2, i)) + (dp[i-1] * 2);
    }

    private static long getOne(long num) {
        long copy = num;

        long cnt = 0;
        for (int i = 55; i > 0; i--) {
            if (((1L << i) & num) > 0) {
                copy -= (1L << i);
                cnt += dp[i-1] + (copy + 1);
            }
        }
        if ((num & 1) > 0) cnt++;
        return cnt;
    }
}