41. 연속된 자연수의 합

작성한 코드 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
    // 	freopen("input.txt", "rt", stdin);
    int n, i, p1 = 1, p2 = 1, sum = 0, cnt = 0;

    scanf("%d", &n);

    while (n / 2 + 1 >= p1)
    {
        p2 = p1 + 1;
        while (n / 2 + 2 >= p2)
        {
            sum = 0;
            for (i = p1; i < p2; i++)
            {
                sum += i;
                if (sum > n)
                    break;
            }
            if (sum == n)
            {
                printf("%d ", p1);
                for (i = p1 + 1; i < p2; i++)
                {
                    printf("+ %d ", i);
                }
                printf("= %d\n", sum);
                cnt++;
            }
            p2++;
        }
        p1++;
    }
    printf("%d", cnt);
    return 0;
}

n^3의 약간 전체 탐색(이러면 안된다...) 쓸데없이 복잡해 보인다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
    // 	freopen("input.txt", "rt", stdin);

    int a, b = 1, cnt = 0, tmp, i;
    scanf("%d", &a);
    tmp = a;
    a--;
    while (a > 0)
    {
        b++;
        a = a - b;
        if (a % b == 0)
        {
            for (i = 1; i < b; i++)
            {
                printf("%d + ", (a / b) + i);
            }
            printf("%d = %d\n", (a / b) + i, tmp);
            cnt++;
        }
    }
    printf("%d\n", cnt);

    return 0;
}

예를 들어 n=15라 하면, 

7 + 8 = 15 는 1 + 2 + (15- (1+2))/2 * 2 = 3 + 12

4 + 5 + 6 = 15 는 1 + 2 + 3+ (15-(1+2+3))/3 * 3 = 6 + 9 이런식으로 나타낼 수 있다. 

1 + 2 + 3 + 4 는 (15-(1+2+3+4))/4 가 자연수가 아니므로 없음.

1 + 2 + 3 + 4 + 5 = 15 ( 위 코드에서는 a=0, b=5인 경우)

 

즉, (n- (1+2+3..+m)) % m == 0 이면 1 + 2 + 3 .. + m + (n-(1+ 2..+m))/m * m = n 으로 나타낼 수 있음.