C++에서 1부터 N까지의 모든 수를 합으로 표현하기 위해 필요한 최소 숫자 개수

문제 개요

정수 N이 주어졌을 때, N을 K개의 정수의 합으로 표현하고, 이 정수들 중 일부 또는 전체를 더하여 1부터 N까지 범위의 모든 수를 만들어야 합니다. 이때 구해야 하는 것은 가능한 한 작은 K값입니다.

핵심 아이디어

K개의 정수가 있을 때 각각을 '더한다 / 더하지 않는다' 두 가지로 선택할 수 있으므로, 만들어 낼 수 있는 서로 다른 합은 공집합을 제외하고 최대 2^K − 1개입니다. 따라서 다음 조건을 만족하는 최소 K를 찾으면 됩니다.

2^K − 1 ≥ N

흥미롭게도 이 최소 K값은 N을 이진수로 표현했을 때의 비트 개수와 정확히 일치합니다. 예를 들어 N = 8은 이진수로 1000이므로 비트가 4개이고, 필요한 최소 정수 개수 역시 4입니다.

예시

N = 8인 경우, 정수 1, 2, 3, 4를 선택하면 다음과 같이 1부터 8까지의 모든 수를 표현할 수 있습니다.

1 = 1
2 = 2
3 = 3
4 = 4
5 = 1 + 4
6 = 2 + 4
7 = 3 + 4
8 = 1 + 3 + 4

따라서 이 경우 정답은 K = 4입니다.

알고리즘

풀이는 의외로 간단합니다. 주어진 정수의 이진 표현에서 비트 개수를 세면 그것이 곧 답입니다. 오른쪽 시프트 연산자(>>)를 반복해서 적용하며, N이 0이 될 때까지 몇 번 반복했는지 세면 됩니다.

C++ 구현

#include <bits/stdc++.h>
using namespace std;

int getMinNumbers(int n) {
    int cnt = 0;
    while (n) {
        ++cnt;
        n = n >> 1;
    }
    return cnt;
}

int main() {
    int n = 8;
    cout << "Minimum required numbers = " << getMinNumbers(n) << endl;
    return 0;
}

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

출력 결과

Minimum required numbers = 4

복잡도 및 정리

N을 반복적으로 절반씩 줄여 가며 비트 수를 세므로 시간 복잡도는 O(log N)이며, 추가 메모리 사용량은 O(1)로 매우 효율적입니다. 요약하면, 1부터 N까지의 모든 수를 부분합으로 표현하기 위해 필요한 최소 정수 개수는 ⌈log₂(N + 1)⌉, 즉 N의 이진수 비트 길이와 같습니다.