숫자 n이 입력으로 주어지면, 조건 (n XOR x) = (n − x)를 만족하는 값 x의 개수를 구하는 것이 목표입니다. 이때 x는 [0, n] 범위 안에 있어야 합니다.
예제로 이해하기
입력 − n = 10
출력 − (n XOR x) = (n − x)를 만족하는 x ≤ n 값의 개수: 4
설명 − 10 xor x = 10 − x를 만족하는 x의 값은 0, 2, 8, 10입니다.
입력 − n = 15
출력 − (n XOR x) = (n − x)를 만족하는 x ≤ n 값의 개수: 16
설명 − 15 xor x = 15 − x를 만족하는 x의 값은 0부터 15까지의 모든 정수입니다.
방법 1: 완전 탐색(Brute Force)
가장 직관적인 방법은 반복문을 이용하는 것입니다. i를 0부터 n까지 하나씩 증가시키며 각 i를 후보 x로 삼고, (n − i == (n ^ i)) 조건을 검사합니다. 조건이 참이면 카운트를 증가시킵니다.
정수 변수 n을 입력받습니다.
함수 count_values(int n)은 조건을 만족하는 x의 개수를 반환합니다.
카운트 변수 count의 초기값을 0으로 설정합니다.
for 반복문으로 i를 0부터 n까지 순회합니다.
각 i에 대해 (n - i == (n ^ i)) // XOR 연산인지 확인합니다.
조건이 참이면 count를 1 증가시킵니다.
반복이 끝나면 count를 결과로 반환합니다.
이 방법의 시간 복잡도는 O(n)입니다.
방법 2: 효율적인 접근 (비트 분석)
먼저 n을 이진수로 변환해 생각해 보겠습니다. 각 비트 자리에서 뺄셈이 빌림수 없이 진행되려면 다음 등식이 성립해야 합니다.
1 xor 0 = 1 − 0 = 1
1 xor 1 = 1 − 1 = 0
그러나 n의 해당 비트가 0이고 x의 비트가 1이면, 뺄셈 과정에서 상위 비트로부터 빌림수가 발생하므로 등식이 깨집니다. 즉, x의 1비트는 반드시 n의 1비트와 같은 자리에만 존재해야 합니다.
따라서 n의 이진 표현에서 1의 개수를 p라고 하면, 각 1비트마다 x에 대해 0 또는 1, 두 가지 선택이 독립적으로 가능합니다. 결국 조건을 만족하는 x의 개수는 2p개가 됩니다.
정수 변수 n을 입력받습니다.
함수 count_values(int n)은 조건을 만족하는 x의 개수를 반환합니다.
카운트 변수 count의 초기값을 0으로 설정합니다.
bitset<8>(n).to_string()을 사용해 n을 이진수 문자열 number로 변환합니다.
length = number.length()로 문자열 길이를 구합니다.
for 반복문으로 인덱스 i = 0부터 i < length까지 문자열을 순회하며, '1'을 만날 때마다 count를 증가시킵니다.
최종적으로 count = pow(2, count)를 계산해 조건을 만족하는 x의 개수를 구합니다.
count를 결과로 반환합니다.
이 방법의 시간 복잡도는 O(log n)으로 완전 탐색보다 훨씬 빠릅니다. 참고로 예제 코드의 bitset<8>은 8비트까지만 표현할 수 있으므로, 더 큰 수를 다루려면 bitset의 크기를 늘려야 합니다.
예제 (완전 탐색)
#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
int count = 0;
for (int i = 0; i <= n; i++){
if (n - i == (n ^ i)){
count++;
}
}
return count;
}
int main(){
int n = 25;
cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of values of x <= n for which (n XOR x) = (n – x) are: 8
예제 (효율적인 접근)
#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
int count = 0;
string number = bitset<8>(n).to_string();
int length = number.length();
for (int i = 0; i < length; i++){
if (number.at(i) == '1')
{ count++; }
}
count = (int)pow(2, count);
return count;
}
int main(){
int n = 25;
cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of values of x <= n for which (n XOR x) = (n – x) are: 8