문제 개요
두 개의 정수 k와 n이 주어졌다고 가정해 봅시다. 우리의 과제는 1부터 n까지 범위 내의 모든 숫자 쌍에 대해 세 가지 비트 연산, 즉 비트 AND(&), 비트 OR(|), 비트 XOR(^)을 수행하고, 그 결과값 중 주어진 값 k보다 작은 값들만 대상으로 각 연산별 최댓값을 찾아 반환하는 것입니다.
예를 들어 입력이 n = 5, k = 5라면 출력은 4 3 4가 됩니다.
5 미만의 숫자 쌍들 사이에서 수행한 AND, OR, XOR 연산의 최댓값은 각각 4, 3, 4입니다. 이 세 값 모두 주어진 값 k인 5보다 작다는 것을 확인할 수 있습니다.
해결 접근 방법
이 문제는 브루트 포스(Brute Force) 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- andMax = 0, orMax = 0, xorMax = 0으로 초기화합니다.
- 임시 변수 value1, value2, value3을 0으로 초기화합니다.
- i를 1부터 n까지 반복하면서, j를 i+1부터 n까지 반복합니다. (자기 자신과의 연산은 제외)
- value1에는 i AND j의 결과를, value2에는 i OR j의 결과를, value3에는 i XOR j의 결과를 저장합니다.
- value1이 현재 andMax보다 크고 k보다 작다면 andMax를 value1로 갱신합니다.
- value2가 현재 orMax보다 크고 k보다 작다면 orMax를 value2로 갱신합니다.
- value3이 현재 xorMax보다 크고 k보다 작다면 xorMax를 value3으로 갱신합니다.
- 모든 반복이 끝나면 andMax, orMax, xorMax를 순서대로 출력합니다.
C 언어 구현 예제
아래 코드를 통해 실제 구현 방법을 더 잘 이해할 수 있습니다.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void solve(int n, int k) {
int andMax = 0, orMax = 0, xorMax = 0;
int value1 = 0, value2 = 0, value3 = 0;
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
value1 = i & j;
value2 = i | j;
value3 = i ^ j;
if (value1 > andMax && value1 < k)
andMax = value1;
if (value2 > orMax && value2 < k)
orMax = value2;
if (value3 > xorMax && value3 < k)
xorMax = value3;
}
}
printf("%d %d %d ", andMax, orMax, xorMax);
}
int main() {
solve(5, 5);
return 0;
}입력
5, 5
출력
4 3 4
코드 설명 및 시간 복잡도
solve 함수는 두 개의 중첩된 for 루프를 사용하여 1부터 n까지의 모든 서로 다른 숫자 쌍 (i, j)을 생성합니다. 각 쌍에 대해 AND, OR, XOR 연산을 수행한 뒤, 그 결과가 기존 최댓값보다 크면서 동시에 k보다 작은 경우에만 해당 최댓값 변수를 갱신합니다.
이 알고리즘의 시간 복잡도는 O(n²)입니다. 모든 가능한 숫자 쌍을 한 번씩 검사하기 때문입니다. n의 크기가 크지 않은 경우에는 충분히 효율적으로 동작하지만, n이 매우 커진다면 비트 연산의 성질을 활용한 최적화 방법을 고려해 볼 수 있습니다.
예제 실행 결과에서 확인할 수 있듯이, n = 5일 때 5 미만의 숫자 쌍 중 AND 연산의 최댓값은 4(예: 4 AND 5 = 4), OR 연산의 최댓값은 3(예: 1 OR 2 = 3), XOR 연산의 최댓값은 4(예: 1 XOR 5 = 4)로 계산되며, 세 값 모두 조건인 k = 5보다 작습니다.