[백준] 9527 : 1의 개수 세기 (DP, 비트마스킹, 누적합) - JAVA

class 5

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

 

 

 

# 문제

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

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

 

# 예제

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

2 12

 

출력

21

 

# 필요개념

이 문제에서는 입력값의 범위가 int를 넘어가기 때문에, long을 사용해주어야 한다. 이는 숫자가 정말 ! 커진다는 것이다.

처음 문제를 풀 때, 비트마스킹을 이용할 생각은 없었고 그냥 dp와 누적합을 이용할 생각이었다. 

 

비트

비트(Bit)는 우리가 아는 1과 0으로 숫자를 표현하는 것을 의미한다. 0과 1은 그대로 0, 1로 표기하고, 2부터 달라진다. 기본적인 것이라서 간단하게 예시만 적어두려고 한다.

2	3	4	5	6	7	8	9	10
10	11	110	101	110	111	1000	1001	1010

 

 

비트 연산자

코드를 작성할 때 많이 사용하게 되는 비트 연산자를 정리해보려고 한다.

구분	연산자	의미	설명
비트연산자	&	비트단위의 AND	두 정수를 한 비트씩 비교 - 양쪽 비트가 모두 1이면 1 - 나머지는 0 반환
	|	비트단위의 OR	두 정수를 한 비트씩 비교 - 양쪽 비트 중 하나라도 1이면 1 - 나머지는 0 반환
	^	XOR	두 정수를 한 비트씩 비교 - 서로 다르면 1 - 같으면 0 반환
	~	NOT	1이면 0으로, 0이면 1로 변경
비트 이동연산자	<<	정수 a를 왼쪽으로 b비트만큼 이동 -> 빈자리는 0으로 채워짐
	>>	정수 a를 오른쪽으로 b비트만큼 이동
	>>>	정수 a를 오른쪽으로 b비트만큼 이동 (빈자리는 무조건 0으로 채워짐)

 

 

비트마스크

컴퓨터는 모든 자료를 이진수로 표현하기 때문에, 이진수를 이용해 연산하면 연산속도를 올릴 수 있다. 이를 이용해 자료구조를 쓰는 기법이 바로 비트마스크이다!

 

비트마스크를 이용하면 연산속도를 올릴 수 있고, 더 적은 메모리를 사용할 수 있다. 

 

 

위 특성을 이용해 문제를 풀 수 있었다.

---

문제를 푼 방법은 아래와 같다.

• dp를 이용해 누적합을 구한다.
  • dp[0]에는 한자리수로 표현하는 비트들의 1의 개수 -> 가능한 케이스가 0, 1 이므로 누적합 : 1
  • dp[1]에는 맨 앞자리가 1이고 두자리수로 표현하는 비트들의 1의 개수
    • 가능한 케이스 : 11,10 이므로 3개 가능
    • dp[0]이 1이었으므로 누적합: 1 + 3 = 4
  • dp[2]에는 맨 앞자리가 2이고 세자리수로 표현하는 비트들의 1의 개수
    • 가능한 케이스 : 111, 110, 101, 100 이므로 8개 가능
    • dp[1]이 4였으므로 누적합: 4 + 8 = 12

이렇게 했을 때, 점화식은 다음과 같이 쓸 수 있다.

DP[N] = 2 * DP[N - 1] + 2 ^ N

 

이유는 종이에 쓰다보면.... 쉽게 끌어낼 수 있다 ㅎ ㅎ

 

이 점화식을 이용해 그냥 풀어내려 하면 2 ^ N부분 때문에 코드를 아래처럼 pow함수를 이용해주어야 한다. 

dp[i] = dp[i - 1] * 2 + Math.pow(2, i);

 

그런데 숫자의 크기가 매우 클 때에는 pow가 정확하게 계산되지 않았다.

 

그래서 결국 비트마스크를 도입했다 .. 

• 곱하기 2 하는 작업 대신 1 << 1 를 사용한다. -> 비트를 왼쪽으로 한 칸 옮기면 2를 곱하는 작업과 같다
• 1의 개수를 구하는 건 & 1 을 이용한다 -> 한 비트씩 비교하며 양 비트가 모두 1이면 1 반환

그래서 비트를 이용한 점화식은 아래와 같다.

dp[i] = (dp[i - 1] << 1) + (1L << i);

 

 

이제 주어진 수(N)를 이용해 1부터 N까지 1의 누적합을 구해주는 함수를 구현한다. 이렇게 구현하면 A와 B가 주어졌을 때, B의 누적합 - (A - 1)의 누적합을 구하면 답을 끌어낼 수 있다.

 

해당함수의 로직은 다음과 같다.

• Long.toBinaryString() 함수를 이용해 숫자를 비트문자열로 바꾼 후 문자열의 길이를 구한다. (문자열을 순회할 예정)
• for문을 위에서 구한 문자열 길이만큼 돈다.
  • 가장 왼쪽 문자부터 1인지 아닌지 체크한다. 이 과정에서도 비트연산자를 사용한다.
  • 1이면 누적합을 cnt에 더해준다
    • 1011 이면 000 ~ 111 의 누적합 + 1000 (8) ~ 1011(11) 의 개수를 더한다.

 

자세한 코드는 아래 첨부할 예정이다.

 

# Code

import java.io.*;
import java.util.*;
public class Main {
    static long[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        int blen = Long.toBinaryString(B).length();
        dp = new long[blen + 1]; // 1 ~ 2^N까지 누적합

        dp[0] = 1;
        for (int i = 1 ; i <= blen ; i++) {
            dp[i] = (dp[i - 1] << 1) + (1L << i);
        }

        long ans = sum(B) - sum(A - 1);
        System.out.println(ans);
    }

    private static long sum(long b) {
        long cnt = b & 1; // b의 1의 개수
        int size = Long.toBinaryString(b).length();
        for (int i = size ; i > 0 ; i--) {
            if ((b & (1L << i)) != 0L) {
                cnt += dp[i - 1] + (b - (1L << i) + 1);
                b -= (1L << i);
            }
        }
        return cnt;
    }
}

 

 

 

# 결과