[알고리즘 연습] 연속된 자연수의 합 (by. C++)

연속된 자연수의 합

• 양의 정수 N이 입력
• 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법 출력
• 예 : N=15이면 7+8=15, 4+5+6=15, 1+2+3+4+5=15 총 3가지의 경우가 존재한다.
• 각 경우의 수도 '1 + 2 + 3 + 4 + 5 = 15'의 형태로 출력할 것 (마지막에 경우의 수 출력)

---

풀이1 (단순접근)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, i, p1=1, p2=2, sum, check=0;

    cin >> n;

    while (p1<p2) {
        sum=0;
        for(i=p1; i<=p2; i++) {
            sum += i;
        }

        if (sum < n) {
            p2++;
        } else if (sum > n) {
            p1++;
        } else {
            cout << p1;
            for(i=p1+1; i<=p2; i++) {
                cout << " + " << i; 
            }
            cout << " = " << n << endl;
            check++;
            p1++;
            p2++;
        }
    }

    cout << check;

    return 0;
}

• 포인터 2개를 활용해 합을 체크하는 방식을 사용했다. (p1~p2까지의 합을 체크)
• 합을 체크해서 합이 n보다 크면 p1을 늘려주고, 합이 N보다 작으면 p2를 늘려준다.
• 합이 n과 일치하면 경우의 수를 체크하는 변수인 check를 1늘려주고, p1과 p2도 1씩 늘려준다.

---

풀이2 (수리적 접근)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, num, i, check=0;

    cin >> n;

    m = 2;
    num = n-1-2;

    while(num>=0) {
        if (num%m==0) {
            cout << 1 + (num/m);
            for(i=2; i<=m; i++) {
                cout << " + " << i + (num/m);
            }
            cout << " = " << n << endl;
            check++;
        }
        m++;
        num -= m;
    }

    cout << check;

    return 0;
}

• 가능한 연속된 숫자의 개수를 이반으로 체크하는 방법도 있다. 이를 m이라 하자.
• n에서 1~m을 차례대로 뺀다. 해당 결과를 num이라고 하자.
• num을 m으로 나눈다.
• 이 때 나누어 떨어지면 연속된 숫자의 합으로 n을 만들 수 있다는 것이다.
• 이는 '연속'하려면 특정값에서 1부터 차례대로 더해져 만들어진 값들이어야 한다는 점을 이용한 것이다.
• m은 1씩 상승하고(연속), 이 때 num은 상승된 m만 추가로 빼면된다. 따라서 처음에 m을 2로, num은 n-1-2로 설정하여 이를 반복활용한다.