알고리즘 (PS)/BOJ
[백준] 9527 - 1의 개수 세기(Counting ones) (G2)
https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net class5 문제를 풀면서 만났던 생 수학 문제. 두 정수가 주어질 때, 두 정수를 포함하는 범위의 모든 정수를 이진수로 변환했을 경우 1의 개수를 모두 세는 문제이다. 곧이곧대로 구하면 수의 범위가 커서 시간초과를 받는다. 나는 다음과 같은 풀이를 떠올렸다. 1. 누적합 [a, b] 구간의 모든 정수의 이진수의 1의 개수를 직접 구하기보다 [1, a] 구간의 이진수의 1..
