문제 개요
세 개의 양의 정수 a, b, c가 주어졌을 때, a와 b의 일부 비트를 뒤집어 (a OR b == c) 조건을 만족하도록 만들어야 합니다. 여기서 OR는 비트별(bitwise) OR 연산을 의미합니다.
뒤집기(flip) 연산이란 숫자의 이진 표현에서 단일 비트를 1에서 0으로, 또는 0에서 1로 변경하는 것입니다. 예를 들어 a = 0010, b = 0110, c = 0101이라면, 적절히 비트를 뒤집은 후 a는 0001이 되고 b는 0100이 되어 (a OR b) = 0101 = c를 만족하게 됩니다.
해결 접근 방법
이 문제는 각 비트 자리를 독립적으로 검사하는 방식으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- 정답 변수 ans := 0으로 초기화합니다.
- i를 0부터 31까지 반복하며 각 비트 위치를 확인합니다.
- bitC := (c / 2^i) AND 1
- bitA := (a / 2^i) AND 1
- bitB := (b / 2^i) AND 1
- 만약 (bitA OR bitB)가 bitC와 다르다면:
- bitC가 0인 경우: bitA = 1이고 bitB = 1이면 두 비트 모두 0으로 바꿔야 하므로 ans에 2를 더하고, 그렇지 않으면 ans에 1을 더합니다.
- bitC가 1인 경우(a와 b의 해당 비트가 모두 0): 둘 중 하나를 1로 바꿔야 하므로 ans에 1을 더합니다.
- 반복이 끝나면 ans를 반환합니다.
여기서 핵심 포인트는 bitC가 0일 때 bitA와 bitB가 모두 1이라면 두 번의 뒤집기가 필요하다는 점입니다. OR 연산의 특성상 하나만 0으로 바꾸면 결과는 여전히 1이 되기 때문입니다.
예제 코드(C++)
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minFlips(int a, int b, int c) {
int ans = 0;
for(int i = 0; i < 32; i++){
int bitC = (c >> i) & 1;
int bitA = (a >> i) & 1;
int bitB = (b >> i) & 1;
if((bitA || bitB) != bitC){
if(!bitC){
if(bitA == 1 && bitB == 1){
ans += 2;
}
else {
ans += 1;
}
}
else{
ans += 1;
}
}
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.minFlips(2,6,5));
}
입력
2 6 5
출력
3
출력 결과 분석
a = 2(0010), b = 6(0110), c = 5(0101)일 때를 비트별로 살펴보겠습니다.
- 비트 0: a = 0, b = 0 → OR 결과는 0, 하지만 c는 1 → 한 비트를 1로 뒤집기 필요 (1회)
- 비트 1: a = 1, b = 1 → OR 결과는 1, 하지만 c는 0 → 두 비트 모두 0으로 뒤집기 필요 (2회)
- 비트 2: a = 0, b = 1 → OR 결과는 1, c도 1 → 변경 불필요
따라서 총 뒤집기 횟수는 1 + 2 = 3이 됩니다.