C++에서 주어진 숫자가 처음 n개 자연수의 합인지 확인하는 방법

이 문제에서는 하나의 숫자 num이 주어집니다. 우리가 해야 할 일은 주어진 숫자가 처음 n개의 자연수의 합인지 판별하는 것입니다.

문제 설명

주어진 숫자가 1부터 n까지 자연수를 모두 더한 값과 일치하는지 확인하고, 일치한다면 그때의 n 값을 찾아야 합니다.

예시로 문제 이해하기

입력: num = 55

출력: Yes, 10

설명:

55는 처음 10개의 자연수를 더한 값입니다. 즉, 1+2+3+4+5+6+7+8+9+10 = 55 입니다.

해결 방법 1: 반복문 활용

가장 단순한 접근 방법은 n을 1부터 하나씩 늘려가며 자연수의 합을 계산하고, 그 합이 num과 같거나 커질 때까지 반복하는 것입니다.

• 합이 num과 같다면 해당 n을 반환합니다.
• 반복 중 합이 num보다 커지면, 주어진 숫자는 자연수의 합이 아니므로 -1을 반환합니다.

예제 프로그램

#include <iostream>
using namespace std;

int isNatSum(int num){

    int sum = 0;
    for (int n = 1; sum < num; n++) {
        sum += n;
        if (sum == num)
            return n;
    }
    return -1;
}

int main(){

    int num = 55;
    int n = isNatSum(num);
    if(n == -1)
        cout<<"The value is not sum of natural numbers";
    else
        cout<<"The value is a sum of first "<<n<<" natural numbers";
    return 0;
}

출력

The value is a sum of first 10 natural numbers

이 방법도 충분히 좋지만, 자연수의 합에 대한 수학 공식을 활용하면 더 효율적으로 문제를 해결할 수 있습니다.

해결 방법 2: 수학 공식 활용

처음 n개의 자연수의 합은 다음 공식으로 계산됩니다.

sum = n × (n+1) / 2

여기서 우리는 sum 값을 알고 있고, n 값을 찾아야 합니다. 따라서 이차방정식을 세워 n을 구할 수 있습니다.

• => 2 × sum = n² + n
• => n² + n − 2 × sum = 0 (이차방정식)

근의 공식을 적용하면 이 이차방정식의 해는 다음과 같습니다.

n = (−1 + √(1 + 8 × num)) / 2

계산된 n이 정수라면 num은 자연수의 합이 맞고, 정수가 아니라면 자연수의 합이 아닙니다.

예제 프로그램

#include <iostream>
#include <math.h>
using namespace std;

int isNatSum(int num){

    int n = ( -1+ sqrt (1 + (8*num) ))/2;
    if(ceil(n)==floor(n)){
        return n;
    }
    return -1;
}

int main(){

    int num = 55;
    int n = isNatSum(num);
    if(n == -1)
        cout<<"The value is not sum of natural numbers";
    else
        cout<<"The value is a sum of first "<<n<<" natural numbers";
    return 0;
}

출력

The value is a sum of first 10 natural numbers

마무리

반복문을 사용하는 첫 번째 방법은 시간 복잡도가 O(√num)인 반면, 이차방정식의 근의 공식을 활용하는 두 번째 방법은 O(1)의 상수 시간에 결과를 얻을 수 있어 훨씬 효율적입니다. 큰 숫자를 다룰 때는 수학적 접근 방식을 사용하는 것이 좋습니다.