Algorithm - Sum Of Consecutive Natural Numbers

연속된 자연수의 합

• 이 문제는 K 라는 수가 주어지고, 그 안에서 N 이라는 자연수가 있을 때,

• K 안에서 연속되는 자연수의 합이 N 이 되는게 몇 가지인지 확인하는 문제이다.

• 이 문제는 Two Pointers 로 풀거나, 수학적 기법으로 푸는 2가지 방법이 있다.

• 먼저 Two Pointers 로 푸는 코드이다.

    public static int twoPointersAlgorithm(int n) {
  
       int answer = 0;
       int sum = 0;
       int pS = 1;
       int m = (n-1)/2;
  
       for ( int pE = 1; pS <= m; pE ++ ) {
           sum += pE;
           if ( sum == n ) answer ++;
           while ( sum >= n ) {
               sum -= pS;
               pS ++;
               if ( sum == n ) answer ++;
           }
       }
       return answer;
   }
  

• 다음은 수학적으로 푸는 방법이다.

• 해당 수를 만들기 위해 연속된 수를 몇개 더해야하는지 그 개수를 세면서 푸는 방법이다.

• 즉, 2개 3개 4개 5개… 이렇게 만드는 방법인데,

• 예를 들어 2개로 가능한지 확인하려면, 우리가 원하는 숫자 n에서 -1, -2를 해준 후 남은 n을 2로 나눠서 딱 나눠 떨어지면 연속된 값이다.

• 15를 예로들면 15-1 하면 14, 14-2 하면 12가 된다. 그리고 12 % 2 == 0 이므로 연속된 합이 15가 되는 숫자가 된다.

• 뺀 숫자에 나눈 숫자 몫을 더한다는 개념이다. 1 + ( 12 / 2 ), 2 + ( 12 / 2 )니까 이건 7 + 8이다.

• 이런 방식으로 3개일 때, 4개일 때, 5개일 때 . . . 해서 n이 0보다 작거나 같아질때까지 진행하면 된다.

   public static int mathAlgorithm(int n) {
       int answer = 0;
       int cnt = 1;
  
       n--;
       while ( n > 0 ) {
           cnt ++;
           n -= cnt;
           if ( n % cnt == 0 ) answer ++;
       }
  
       return answer;
   }