[백준 알고리즘] 9527번 자바(Java) 1의 개수 세기

조건

문제

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

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

 

입력

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

출력

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

 

풀이

• 10^16값을 다 저장하는게 메모리상 불가능하므로 누적합을 이용해서 저장해야한다
• ex. 12이면 2[2]까지의 누적합 12를 더해준다.
• 근데 이제 8~12의 값을 규칙을 토대로 구해야하는데 이걸 타 블로그에서는 비트마스크 방식을 채택했다
• 본인은 그방식과 다르게 2로 나눠서 남은 누적합을 구한 이후 추후 더하는 방식을 채택했다

누적합 과정

 

숫자 n에 대한 정확한 이진수 합 구하는 과정

 

 

위 그림에서 나눠진 12~15숫자, 이진수합 12를 다시 또 2개 구역으로 나누는 과정

• 이와같은 방법으로 계속하면 12는 2[2]+(8~11까지의 이진수 1의 값 합)+(12 이진수 1의값) 이 된다
• 12+8+2 = 22가 된다. 이와 같은 방식으로 1도 하면 1이 되고 결국 2~12의 이진수 1의 값 누적합은 21이 된다.

 

예제 입력 예시

2 12

 

예제 출력 예시

21

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//백준 9527번 1의 개수 세기

public class Main {
	
    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());
		
		long sumB = oneCount(B);
		long sumA = oneCount(A-(long)1);
		System.out.println(sumB - sumA);
	}
     
    private static long oneCount(long AB) {
		long[] countNum = new long[55];
		long[] countOne = new long[55];
		
		countNum[0] = 1;
		countOne[0] = 1;
		//추후 10^16값까지 저장
		for (int i = 1; i < countOne.length; i++) {
			countNum[i] = countNum[i-1]*2; 
			countOne[i] = 2*countOne[i-1]+countNum[i-1]; 
		}
		
		long standardB = 0;
		long index = 0;
		long sumNum = 0;
		while(true) {
			standardB += countNum[(int)index];
			if(standardB>AB) {
				break;
			}
			sumNum += countOne[(int)index];
			index++;
		}
		
		//여기서 한번 짜르고 이후에 값을 생각해야함
		long curNum = countNum[(int)index]+countNum[(int)index]/2; //B와 비교할 숫자
		long standardNum = countNum[(int)index]/2; //+=2 계속해줄 숫자
		long standardOne = countOne[(int)index]; //더해주거나 사라질 숫자	
		
		while(standardNum>=0&&AB!=(countNum[(int)index]-1)) {
			standardOne /= 2;
			standardNum /= 2;
			if(curNum<=AB) {
				if(standardNum==0) {
					sumNum+= (standardOne*2+1);
					break;
				}

				sumNum += (standardOne - standardNum);
				standardOne += (standardNum);
				curNum+=standardNum;
			}
			else {
				if(standardNum==0) {
					sumNum+= standardOne;
					break;
				}
				standardOne -= (standardNum);
				curNum-=standardNum;
				if(standardNum==0) {
					break;
				}
			}
		}
		return sumNum;
    }
}

 

 

 

 

문제 출처

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