9527 1의 개수세기
알고리즘(수학)
1
2
3
4
5
6
7
8
9
10
11
12
13
1. 2^n 마다 규칙이 있음
2. f(n)을 2^n ~ 2^(n+1)-1 에서의 1의 개수라고 한다면, f(n) = 2^n + f(i) ( 0 <= i <= n-1 ) 이 성립한다.
3. 그리고 들어오는 수 A,B에 대해
(1~B 까지의 1의 개수) - (1~A-1 까지의 1의 개수) 를 하면 값이 나온다.
4. 2에서의 규칙에따라 end가 주어지면 0에서 end까지의 1의 개수를 구하는 함수를 선언한다.
-> 이때 end 미만의 최대 2^n의 n를 구한다.
-> 2에서의 규칙에 따라 0~n까지의 f(n)을 구한다.
-> 그럼 나머지 2^(n+1) ~ end 에서의 1의 개수를 구하면 된다.
5. 나머지를 구하는 함수를 선언한다. 2^(n+1)에서 end까지 구하면 된다.
-> 이때 2^(n+1) ~ end 사이의 값들의 맨앞은 전부 1이고, 개수는 end - 2^(n+1) + 1이다.
-> 그리고 그 맨앞의 1을 떼고 보면, 0부터 end - 2^(n+1) 까지의 이진수 분포와 동일하다
-> 따라서 다시 end - 2^(n+1)을 위 4번 함수에 넣으면 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cmath>
using namespace std;
long long a, b;
long long DP[55];
long long getN(int N);
long long countOne(long long end);
long long getRest(long long start, long long end);
int main() {
cin >> a >> b;
DP[0] = 1;
cout << countOne(b) - countOne(a-1) << endl;
}
long long countOne(long long end) {
if (end <= 2)
return end;
int n = 0;
long long temp = 1;
while (temp < end) {
temp *= 2;
n++;
}
if (temp - end <=1)
n -= 1;
else
n -= 2;
long long result = 0;
for (int i = 0; i <= n; i++)
result += getN(i);
result += getRest(pow(2, n+1), end);
return result;
}
long long getN(int N) {
if (N == 0)
return 1;
if (DP[N] != 0)
return DP[N];
long long result = pow(2, N);
for (int i = N - 1; i >= 0; i--)
result += getN(i);
return DP[N] = result;
}
long long getRest(long long start, long long end) {
if (start > end)
return 0;
return end - start + 1 + countOne(end - start);
}