[Inflearn] 연속된 자연수의 합

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 최대 N은 1,000 이고, N^2일 경우, 1,000,000 이니깐.. 단순하게 생각해도 될 것 같다.

     N = 15 일 경우,

     N / 2 를 point 로 두고, p = 15 / 2 = 7

     N보다 크거나 같을 때까지 더해준다.

     7 + 8 = 15, N과 같은가? printf()

     p--, cnt++

 

     6 + 7 + 8 = 21 

     p--

 

     5 + 6 + 7 = 18 

     p--

     4 + 5 + 6 = 15, N과 같은가? printf()

     p--, cnt++

     3 + 4 + 5 + 6 = 18

     p--

     2 + 3 + 4 + 5 + 6 = 20

     p--

     1 + 2 + 3 + 4 + 5 = 15 printf()

     p--, cnt++

     

     과정을 보아하니 중복되는 연산이 많다.

     한 마디로 비효율적이다.

  2.  중복되는 연산을 미리 해둔다면 좋지 않을까?

      N/2+1 크기의 배열은 만든 후, ~까지의 합을 구해서 저장해놓는다.

      1    2    3    4    5    6    7     8 

      1    3    6    10   15  21   28  36

      1번 방법처럼 누적합을 구하는데,

      누적합을 구할 때 위 배열을 활용해서 구하는 것이다.

      단, 누적합이 N보다 크거나 같을 때까지 더해준다.

     a[8] - [6] = 15 (7+8)

     printf(), p--, cnt++

 

     a[7] - a[5] = 13 (6 + 7)

     a[8] - a[5] = 21 (6+7+8)

     p--

 

     a[6] - a[4] = 11 (5+6)

     a[7] - a[4] = 18 (5+6+7)

     p--

     a[5] - a[3] = 9 ( 4+5)

     a[6] - a[3] = 15 (4+5+6)

     printf(), p--, cnt++

     a[4] - a[2] = 7 (3+4)

     a[5] - a[2] = 12 (3+4+5)

     a[6] - a[2] = 18 (3+4+5+6)

     p--

    

     a[3] - a[1] = 5 (2+3)

     a[4] - a[1] = 9 (2+3+4)

     a[5] - a[1] = 14 (2+3+4+5)

     a[6] - a[1] = 20 (2+3+4+5+6)

     p--

     

     ... 

     결국 연산량은 같아지네..

     그래도 이런 방법도 있었겠구나.. 라고.. 생각하자..

  3. 강사님 풀이법인데 나에겐 엄청 신박하다..

     N = 15 일 때,

     두 개의 연속된 숫자의 합이 15인 수를 구하는 방법은

     "두 개의 연속된" 이므로 1과 2를 적어본다.

     그 후, 15 - (1 + 2) = 12 인데, 

     두 개의 연속된 숫자의 합을 볼 것이므로 2로 나눠본다. 12%2==0,

     나누어 떨어진다면 두 개의 연속된 숫자로 15를 만들 수 있다는 것이고, 

     12 / 2 = 6 을 1과 2에 분배시켜본다.

     --------

     1    2

     6    6

     --------

     그러면 끝난 것이다. (1 + 6) + (2 + 6) = 15

     즉, 7 + 8 로 15를 만들 수 있다.

     세 개의 연속된 숫자의 합도 마찬가지로 해보다.

     15 - (1+2+3) = 9

     9 % 3 = 0

     9 / 3 = 3

     -------------

     1    2    3

     3    3    3

     -------------

     (1+3)+(2+3)+(3+3) = 15

    네 개의 연속된 숫자의 합까지 해볼까?

     15 - (1+2+3+4) = 5

     5 % 4 = 1

    네개의 연속된 숫자의 합으로 표현될 수 없다.

     다섯개의 연속된 숫자의 합까지 진짜!!

     15 - (1+2+3+4+5) = 0

     0 % 5 = 0

     0 / 5 = 0

     ----------------------

     1    2    3    4    5

     0    0    0    0    0

     ----------------------

     1+2+3+4+5 = 15

#. Code

ㅊ++c++#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    //freopen("input.txt", "rt", stdin);
 
    int n, p, i, j, cnt = 0, sum;
 
    scanf("%d", &n);
 
    p = n / 2;
 
    while (p > 0)
    {
        sum = 0;
 
        for (i = p; i <= n; i++)
        {
            sum += i;
 
            if (sum >= n)
                break;
        }
 
        if (sum == n)
        {
            cnt++;
 
            printf("%d ", p);
 
            for (j = p + 1; j <= i; j++)
                printf("+ %d ", j);
 
            printf(" = %d\n", n);
        }
 
        p--;
    }
 
    printf("%d\n", cnt);
 
    return 0;
}

강사님 풀이대로(3번 풀이) 다시 풀어본 코드이다

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int main(void) {     //freopen("input.txt", "rt", stdin);       int n, i, num = 2, sum, tmp = 1, base, cnt = 0;       scanf("%d", &n);       while (tmp > 0)     {         sum = 0;           for (i = 1; i <= num; i++)             sum += i;           tmp = n - sum;           if (tmp % num == 0)         {             base = tmp / num;               printf("%d ", base + 1);               for (i = base + 2; i <= base + num; i++)                 printf("+ %d ", i);                          printf("= %d\n", n);               cnt++;         }           num++;     }       printf("%d\n", cnt);       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include<stdio.h>   int main(){     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; }   Colored by Color Scripter

cs

똑같은 풀이고 구현한 건데,, 강사님은 역시 더 깔끔하게 구현하셨다..

먼저 나는 아래처럼 1+ 2+ 3... 이렇게 계속 n개의 연속된 수의 합을 구하고 다시 n에서 빼주었는데

for (i = 1; i <= num; i++)

sum += i;

tmp = n - sum;

...

num++;

강사님은 line 8~13 을 보면, 계속 누적해서 빼주고 있다.

tmp=a;

a--;

 

while(a>0){

    b++;

    a=a-b;

    ...

나도 그나마 생각을 더 했었더라면 계속 1부터 더해주지 말고,

누적주었더라면 더 효율적이었을 텐데..!

중복되는 연산은 최대한 줄여보자라는 생각으로 구현하도록 노력해보자.

출력해주는 부분에서도 내가 번거롭게 짰던 부분들을 잘 참고해야겠다.

#. Result

  - Input --------------------------------------------------------

15

------------------------------------------------------------------

  - Output --------------------------------------------------------

7 + 8 = 15 

4 + 5 + 6 = 15 

1 + 2 + 3 + 4 + 5 = 15 

3

------------------------------------------------------------------