두 개의 숫자 N과 K가 주어졌을 때, 각각 2의 거듭제곱이면서 그 합이 정확히 N이 되는 K개의 숫자를 출력하는 것이 과제입니다. 만약 그런 조합을 만드는 것이 불가능하다면 -1을 반환해야 합니다.
예를 들어 N = 9, K = 4라고 가정해 보겠습니다. 이때 출력은 4 2 2 1이 됩니다. 이 네 숫자의 합은 9이고, 원소의 개수는 4개이며, 모든 숫자가 2의 거듭제곱이라는 조건을 만족합니다.
문제 해결 접근 방법
이 문제는 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 가장 큰 2의 거듭제곱 하나를 반으로 나누면 같은 값 두 개(즉, 두 개의 2의 거듭제곱)가 되고, 전체 합은 변하지 않으면서 원소의 개수만 1개 늘어납니다. 이 성질을 반복적으로 적용하는 것입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- N의 이진 표현에서 설정된 비트(set bit)의 개수보다 k가 작거나, k가 N보다 크다면 -1을 반환합니다. 설정된 비트의 개수는 만들 수 있는 최소 원소 개수이고, N 자체(모두 1로 분해)는 최대 원소 개수이기 때문입니다.
- N의 설정된 비트 위치에 해당하는 2의 거듭제곱 값을 우선순위 큐에 삽입합니다.
- 우선순위 큐의 원소 개수가 k에 도달할 때까지 다음 과정을 반복합니다. 큐에서 가장 큰 원소를 꺼냅니다.
- 꺼낸 원소를 2로 나눈 값을 두 번 우선순위 큐에 다시 삽입합니다. 이렇게 하면 원소 개수가 1씩 증가하고 합은 그대로 유지됩니다.
- k개의 원소가 확보되면 큐의 내용을 모두 출력합니다.
예제 코드
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
void displayKnumbers(int n, int k) {
// N의 설정된 비트 개수 계산
int set_bit_count = __builtin_popcount(n);
// 불가능한 경우 판별
if (k < set_bit_count || k > n) {
cout << "-1";
return;
}
priority_queue<int> queue;
int two = 1;
// 설정된 비트 위치의 2의 거듭제곱을 큐에 삽입
while (n) {
if (n & 1) {
queue.push(two);
}
two = two * 2;
n = n >> 1;
}
// 원소 개수가 k에 도달할 때까지 가장 큰 원소를 반으로 분할
while (queue.size() < k) {
int element = queue.top();
queue.pop();
queue.push(element / 2);
queue.push(element / 2);
}
// 결과 출력
int ind = 0;
while (ind < k) {
cout << queue.top() << " ";
queue.pop();
ind++;
}
}
int main() {
int n = 30, k = 5;
cout << "Numbers are: ";
displayKnumbers(n, k);
}실행 결과
Numbers are: 8 8 8 4 2
동작 원리 살펴보기
위 예제에서 N = 30의 이진 표현은 11110입니다. 따라서 초기 상태에서 우선순위 큐에는 16, 8, 4, 2가 들어가며 원소는 4개입니다. k = 5이므로 한 번의 분할이 더 필요합니다. 가장 큰 값인 16을 꺼내 8과 8로 나누어 다시 삽입하면 큐에는 8, 8, 8, 4, 2가 남고, 이것이 바로 합이 30인 5개의 2의 거듭제곱입니다.
시간 복잡도
초기화 단계에서 N의 비트를 확인하는 데 O(log N), 분할 반복은 최대 (K − 설정된 비트 수)번 발생하므로 전체 시간 복잡도는 O(K log K + log N)으로 볼 수 있습니다. 우선순위 큐의 삽입과 삭제 연산이 로그 시간에 처리되기 때문에 입력 크기가 커져도 효율적으로 동작합니다.