[BOJ] 9527 1의 개수 세기 (C/C++)

9527번: 1의 개수 세기

문제

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

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

입력

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

출력

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

---

문제를 보자마자 저번에 풀었던 문제가 생각났다. 그때는 십진법으로 모든 숫자를 셌었지만 이번엔 이진법의 1의 개수만 센다. 

[BOJ] 1019 책 페이지

일단 A와 B 사이의 1의 개수를 세는건 저번과 동일하게 A까지의 1, B까지의 1을 따로 구하고 계산하면 되겠다 싶었다. 그럼 그다음 문제는 1을 어떻게 세느냐다. 저번처럼 어떤 숫자까지 그냥 가고 그 밑으로는 주르륵 구해질 것 같았는데, 그 구체적인 방법을 떠올리는 게 쉽지 않았다. 그래서 다른 사람의 블로그를 참고해서 문제를 풀 수 있었다. 이 블로그가 가장 친절하게 설명되어 있었던 것 같다.

 

[BOJ] 백준 9527 1의 개수 세기

 

long long형인 1을 표현하는 방법으로 (long long)1을 사용하는 방법도 있겠지만, 이 코드에서는 1LL을 사용했다. 훨씬 간편하고 괄호때문에 오타를 낼 일도 없을 것 같다. 무엇보다 키보드를 쉬프트 누르는 것까지 포함한다면 4번만 누르면 된다.

 

	#include <iostream>
	#define MAX 55
	using namespace std;
	long long power2[MAX];
	long long A, B;
	long long getOne(long long x) {
	long long ret = x & 1;
	for (int i = MAX - 1; i > 0; i--) {
	if (x & (1LL << i)) {
	ret += power2[i - 1] + (x - (1LL << i) + 1);
	x -= 1LL << i;
	}
	}
	return ret;
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> A >> B;
	power2[0] = 1;
	for (int i = 1; i < MAX; i++) {
	power2[i] = 2 * power2[i - 1] + (1LL << i);
	}
	cout << getOne(B) - getOne(A - 1);
	return 0;
	}

view raw 9527.cpp hosted with ❤ by GitHub

 

후기)

언제나 수학 태그가 달려있는 문제는 어렵게 느껴진다. 사실 요새 푼 플레문제들보다도 이게 더 어려운 것 같은데 사람은 난이도를 쉽게 주는 것 같다. 수학 태그를 많이 안 풀어봐서 그런 거겠지....? 그런데 알고리즘 대회를 준비하는 게 아니라서 굳이 수학에 익숙해져야 하나 싶다.