[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번만 누르면 된다.

 

 

후기)

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