반응형
https://www.acmicpc.net/problem/15917
15917번: 노솔브 방지문제야!!
어떤 수 a가 2의 거듭제곱꼴로 나타내어진다고 해 봅시다. 그렇다면, a = 2n (단 n ≥ 0인 정수) 를 만족할 겁니다. 보통, 각 비트별로 검사를 하면서, 켜져 있는 비트의 개수를 알아내는 것도 좋은 방법입니다. 이때에는, 많아봤자 32번 정도 연산을 수행하고, 전체 쿼리가 Q개 있다면, 총 시간 복잡도는 O(32Q)가 됩니다. 그런데, 더 좋은 방법이 없을까요? x (x ≥ 0)를 2진법으로 표현해 볼건데요. x가 홀수인 경우와 짝수인 경우로 나
www.acmicpc.net
비트계산에 대한 이해가 필요한 문제입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q;
cin >> q;
while (q--)
{
int a;
cin >> a;
if ((a&(-a)) == a) cout << 1 << '\n';
else cout << 0 << '\n';
}
}
|
cs |
'Algorithm' 카테고리의 다른 글
| (C++) - 백준(BOJ) 2991번 : 사나운 개 (1) | 2020.01.01 |
|---|---|
| (C++) - 백준(BOJ) 14614번 : Caculate! (0) | 2020.01.01 |
| (C++) - 백준(BOJ) 6322번 : 직각 삼각형의 두 변 (0) | 2020.01.01 |
| (C++) - 백준(BOJ) 14909번 : 양수 개수 세기 (0) | 2020.01.01 |
| (C++) - 백준(BOJ) 11134번 : 쿠키애호가 (0) | 2020.01.01 |