문제 소개
길이가 N인 세 개의 이진 수열 A, B, C가 주어집니다. 각 수열은 하나의 이진수를 나타내며, 목표는 A와 B의 비트 중 일부를 뒤집어(flip) A XOR B의 결과가 C와 같아지도록 만드는 데 필요한 최소 뒤집기 횟수를 구하는 것입니다.
XOR 연산의 진리표
먼저 XOR 연산의 진리표(truth table)부터 살펴보겠습니다.
| X | Y | X XOR Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
표에서 확인할 수 있듯이, X와 Y의 값이 서로 같으면 XOR 결과는 0이 되고, 값이 다르면 1이 됩니다. 이 성질을 활용하면 각 자릿수마다 비트를 뒤집어야 하는지 손쉽게 판단할 수 있습니다.
경우의 수 정리
- A[i] == B[i]이고 C[i] == 0인 경우 → 이미 조건을 만족하므로 뒤집을 필요 없음
- A[i] == B[i]이고 C[i] == 1인 경우 → A[i] 또는 B[i] 중 하나를 뒤집고, 뒤집기 횟수 1 증가
- A[i] != B[i]이고 C[i] == 0인 경우 → A[i] 또는 B[i] 중 하나를 뒤집고, 뒤집기 횟수 1 증가
- A[i] != B[i]이고 C[i] == 1인 경우 → 이미 조건을 만족하므로 뒤집을 필요 없음
예제 1
입력
A[] = { 0,0,0,0 }
B[] = { 1,0,1,0 }
C[] = { 1,1,1,1 }출력
필요한 뒤집기 횟수 : 2
설명
A[0] xor B[0] → 0 xor 1 = 1, C[0] = 1 → 뒤집기 불필요
A[1] xor B[1] → 0 xor 0 = 0, C[1] = 1 → 뒤집기 횟수 = 1
A[2] xor B[2] → 0 xor 1 = 1, C[2] = 1 → 뒤집기 불필요
A[3] xor B[3] → 0 xor 0 = 0, C[3] = 1 → 뒤집기 횟수 = 2
예제 2
입력
A[] = { 0,0,1,1 }
B[] = { 0,0,1,1 }
C[] = { 0,0,1,1 }출력
필요한 뒤집기 횟수 : 2
설명
A[0] xor B[0] → 0 xor 0 = 0, C[0] = 0 → 뒤집기 불필요
A[1] xor B[1] → 0 xor 0 = 0, C[1] = 0 → 뒤집기 불필요
A[2] xor B[2] → 1 xor 1 = 0, C[2] = 1 → 뒤집기 횟수 = 1
A[3] xor B[3] → 1 xor 1 = 0, C[3] = 1 → 뒤집기 횟수 = 2
알고리즘 접근 방식
- 배열 a[], b[], c[]에 각각 이진수를 저장합니다.
- 함수 flipCount(int A[], int B[], int C[], int n)은 배열 a, b, c와 길이 n을 입력받아, A XOR B가 C가 되도록 만들기 위해 A[] 또는 B[]의 비트를 뒤집어야 하는 횟수를 반환합니다.
- 변수 count는 뒤집기 횟수를 나타내며 0으로 초기화합니다.
- for 반복문으로 i = 0부터 i < N까지 각 비트를 순회합니다.
- 각 비트에서 A[i]와 B[i]가 같고 C[i]가 1이면 count를 증가시킵니다.
- 각 비트에서 A[i]와 B[i]가 다르고 C[i]가 0이면 count를 증가시킵니다.
- 모든 비트를 검사한 후 count를 결과로 반환합니다.
이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(N)이며, 추가 메모리가 거의 필요하지 않아 공간 복잡도 역시 O(1)로 매우 효율적입니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
int flipCount(int A[], int B[], int C[], int N){
int count = 0;
for (int i=0; i < N; ++i){
// A[i]와 B[i]가 같으면 XOR 결과는 0, 이때 C[i]가 1이면 뒤집기 필요
if (A[i] == B[i] && C[i] == 1)
++count;
// A[i]와 B[i]가 다르면 XOR 결과는 1, 이때 C[i]가 0이면 뒤집기 필요
else if (A[i] != B[i] && C[i] == 0)
++count;
}
return count;
}
int main(){
//N은 전체 비트 개수를 나타냅니다.
int N = 5;
int a[] ={1,0,0,0,0};
int b[] ={0,0,0,1,0};
int c[] ={1,0,1,1,1};
cout <<"A와 B의 XOR이 C와 같아지도록 뒤집어야 할 최소 비트 수 :"<<flipCount(a, b, c,N);
return 0;
}
출력
A와 B의 XOR이 C와 같아지도록 뒤집어야 할 최소 비트 수 : 2
마무리
이 문제는 XOR 연산의 기본 성질만 이해하고 있다면 배열을 한 번 순회하는 것만으로 답을 구할 수 있는 간단하면서도 유용한 유형입니다. 실제 코딩 테스트나 비트 조작(bit manipulation) 관련 문제에서 자주 등장하므로, 위에서 정리한 네 가지 경우의 수를 확실히 익혀두는 것이 좋습니다.