C++로 첫 N개 자연수를 합의 차이가 D인 두 집합으로 나눌 수 있는지 판별하는 방법

문제 개요

이 문제에서는 두 개의 정수 N과 D가 주어집니다. 우리가 해야 할 일은 첫 N개의 자연수(1부터 N까지)를 두 개의 집합으로 나누었을 때, 두 집합에 속한 숫자들의 합 차이가 정확히 D가 될 수 있는지 판별하는 것입니다.

예시

입력: N = 5, D = 3

출력: Yes

설명:

1, 2, 3, 4, 5 중에서
set1 = {1, 2, 3}, set2 = {4, 5}로 나누면,
{4+5} - {1+2+3} = 9 - 6 = 3 으로 차이가 3이 됩니다.

풀이 접근 방법

이 문제는 몇 가지 수학적 계산만으로 해결할 수 있습니다.

두 집합 원소의 합을 각각 sum(s1), sum(s2)라고 하면 다음 두 식이 성립합니다.

• 자연수의 합 공식: sum(s1) + sum(s2) = (n × (n+1)) / 2
• 문제의 조건: sum(s1) - sum(s2) = D

두 식을 서로 더하면 다음과 같습니다.

2 × sum(s1) = ((n × (n+1)) / 2) + D

sum(s1)은 반드시 정수여야 하므로, 위 조건이 성립하려면 ((n × (n+1)) / 2) + D의 값이 짝수일 때만 해가 존재합니다. 따라서 이 값이 2로 나누어떨어지는지만 확인하면 됩니다.

구현 예시

위 풀이를 C++로 구현한 프로그램입니다.

#include <iostream>
using namespace std;

bool isSetPossible(int N, int D) {
    int total = (N * (N + 1)) / 2 + D;
    return (total % 2 == 0);
}

int main() {
    int N = 10;
    int D = 7;
    cout<<"첫 "<<N<<"개의 자연수로 합의 차이가 "<<D<<"인 두 집합 만들기: ";
    isSetPossible(N, D)?cout<<"가능합니다":cout<<"불가능합니다";
    return 0;
}

출력 결과

첫 10개의 자연수로 합의 차이가 7인 두 집합 만들기: 가능합니다

마무리 정리

핵심은 전체 합 S = n(n+1)/2에 주어진 차이 D를 더한 값 (S + D)이 짝수인지 확인하는 것입니다. 이 값이 짝수라면 한쪽 집합의 합을 (S + D) / 2로 맞출 수 있어 두 집합을 만드는 것이 가능합니다. 시간 복잡도는 O(1)로 입력 크기와 무관하게 즉시 판별할 수 있는 매우 효율적인 방법입니다.