BOJ 9527. 1의 개수 세기
랭크 : 골드2
문제 풀이
비트 연산을 통해서 구하는 특정 위치일 때, 밑에 부분은 모두 0으로 만들도록 구현하면서, 위의 부분의 비트 수를 통해 총 합을 구하여, 이를 점점 중첩해나가는 식으로 문제를 풀었습니다. 틀린 부분은 그냥 1로 비트연산을 수행하면 int에 범위 밖을 벗어나는 것에 대해 잡아주지 못하기 때문에 1LL을 비트연산 해주어야 합니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
#define ll long long
ll total = 0;
ll dict[55];
int check_bit(ll tmp) {
int result = 0;
while (tmp) {
if (tmp & 1) result++;
tmp >>= 1;
}
return result;
}
void dfs(ll A, ll B, ll bitB, int step) {
if (A == B) {
total += bitB;
return ;
}
if (A & (1LL << step)) {
ll bitA = check_bit(A);
total += dict[step] + (1LL << step) * bitA;
A += (1LL << step);
}
if (B & (1LL << step)) {
total += bitB;
bitB--;
total += dict[step] + ((1LL << step) - 1LL) * bitB;
B -= (1LL << step);
}
dfs(A, B, bitB, step + 1);
}
int main() {
fastio;
ll A, B;
cin >> A >> B;
dict[1] = 1;
for (int i=2; i<55; i++) {
dict[i] = dict[i-1] * 2 + (1LL << (i-1));
}
dfs(A, B, check_bit(B), 0);
cout << total << endl;
}알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| dp, bitwise | $O(1)$ | $O(1)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 1005. ACM Craft (0) | 2022.07.08 |
|---|---|
| BOJ 1806. 부분합 (0) | 2022.07.07 |
| BOJ 2887. 행성 터널 (0) | 2022.07.07 |
| BOJ 1007. 벡터 매칭 (0) | 2022.07.07 |
| BOJ 2623. 음악프로그램 (0) | 2022.07.06 |