합이 k가 되는 부분 집합이 없도록 최대 개수의 숫자를 선택하는 C++ 프로그램

두 개의 정수 n과 k가 주어졌을 때, 1부터 n 사이의 서로 다른 숫자들을 최대한 많이 선택하되, 선택된 숫자들 중 어떤 부분 집합의 합도 정확히 k가 되지 않도록 하는 문제입니다. 조건을 만족하는 숫자들을 찾았다면 해당 숫자들을 반환하면 됩니다.

예를 들어 n = 5, k = 3이 입력으로 주어진다면, 출력은 [4, 5, 2]가 됩니다.

접근 방법

이 문제는 간단한 수학적 관찰로 해결할 수 있습니다. 합이 k가 되는 부분 집합이 존재하지 않으려면 다음 두 범위의 숫자만 선택하면 됩니다.

(k+1)/2부터 k-1까지의 숫자: 이 범위의 숫자들은 그 자체로는 k보다 작지만, 이 범위에서 두 개 이상을 더하면 항상 k보다 커지므로 안전합니다.
k+1부터 n까지의 숫자: k보다 큰 숫자들은 단독으로도, 다른 양수와 더해도 절대 k가 될 수 없습니다.

반면 1부터 (k+1)/2 - 1까지의 작은 숫자들은 서로 조합되어 합이 k가 될 가능성이 있기 때문에 제외해야 합니다. 이렇게 하면 조건을 만족하면서도 가장 많은 숫자를 선택할 수 있습니다.

알고리즘 단계

문제를 해결하기 위해 다음 단계를 따릅니다.

i := (k + 1) / 2 로 초기화하고, i <= k - 1 인 동안 i를 1씩 증가시키며 반복:
    i 출력
i := k + 1 로 초기화하고, i <= n 인 동안 i를 1씩 증가시키며 반복:
    i 출력

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

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

void solve(int n, int k) {
   for (int i = (k + 1) / 2; i <= k - 1; i++) {
      cout << i << ", ";
   }
   for (int i = k + 1; i <= n; i++) {
      cout << i << ", ";
   }
}
int main() {
   int n = 5;
   int k = 3;
   solve(n, k);
}

입력

5, 3

출력

2, 4, 5,

동작 원리 설명

n = 5, k = 3인 경우를 살펴보겠습니다. 먼저 (k+1)/2 = 2부터 k-1 = 2까지의 숫자인 2를 출력하고, 그다음 k+1 = 4부터 n = 5까지의 숫자인 4와 5를 출력합니다. 결과적으로 선택된 숫자는 {2, 4, 5}입니다.

이 집합의 모든 부분 집합의 합은 2, 4, 5, 6, 7, 9, 11 중 하나이며, 어떤 경우에도 3이 되지 않습니다. 또한 숫자 1은 2와 함께 선택될 경우 1 + 2 = 3이 되어 조건을 위반하므로 제외된 것이며, 이는 선택 가능한 최대 개수인 3개({2, 4, 5})를 유지하면서 조건을 만족하는 유일한 방법 중 하나입니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 추가적인 공간 사용 없이 결과를 바로 출력할 수 있어 매우 효율적입니다.