C++로 1부터 N까지의 자연수를 주어진 차이와 서로소 합 조건을 만족하는 두 집합으로 나누는 방법

개요

이 튜토리얼에서는 1부터 n까지의 자연수를 두 개의 그룹으로 나눌 수 있는지 확인하는 방법을 알아봅니다. 나누기가 가능하려면 다음 두 가지 조건을 반드시 만족해야 합니다.

• 두 그룹의 합의 절대적인 차이가 m이어야 합니다.

• 두 합의 최대공약수(GCD)가 1이어야 합니다. 즉, 두 수가 서로소(코프라임) 관계여야 합니다.

해결 접근 방식

1부터 n까지 자연수의 총합은 (n*(n+1))/2 공식으로 구할 수 있습니다. 전체 합과 목표 차이 m을 이미 알고 있으므로, 이를 이용해 각 그룹의 합인 sumOne과 sumTwo를 계산할 수 있습니다. 아래 연립방정식을 참고하세요.

sumOne + sumTwo = (n*(n+1))/2
sumOne - sumTwo = m

두 식을 정리하면 sumOne = (전체 합 + m) / 2, sumTwo = 전체 합 - sumOne이 됩니다.

예제 코드

먼저 전체 합이 m보다 작으면 나누기가 불가능하므로 false를 반환하고, 그렇지 않으면 두 합의 차이가 m과 일치하는지 확인한 뒤 최대공약수가 1인지 검사합니다.

#include <bits/stdc++.h>
using namespace std;
bool canSplitIntoTwoHalves(int n, int m) {
    int total_sum = (n * (n + 1)) / 2;
    int sumOne = (total_sum + m) / 2;
    int sumTwo = total_sum - sumOne;
    if (total_sum < m) {
        return false;
    }
    if (sumOne + sumTwo == total_sum && sumOne - sumTwo == m) {
        return (__gcd(sumOne, sumTwo) == 1);
    }
    return false;
}
int main() {
    int n = 10, m = 17;
    if (canSplitIntoTwoHalves(n, m)) {
        cout << "Can split";
    }
    else {
        cout << "Can't split";
    }
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

Can split

동작 원리 살펴보기

n=10, m=17인 경우를 예로 들면, 1부터 10까지의 총합은 55입니다. 이때 sumOne은 (55+17)/2 = 36, sumTwo는 55-36 = 19가 됩니다. 두 값의 차이는 정확히 17이고, gcd(36, 19) = 1이므로 두 수는 서로소입니다. 따라서 주어진 조건을 모두 만족하여 두 집합으로 나누는 것이 가능합니다.

결론

이처럼 수학적 공식과 최대공약수 계산만으로도 문제를 효율적으로 해결할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.