[알고리즘]입력받은 수가 연속된 자연수의 합으로 이루어지는 경우의 수

▷ 문제

N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.

만약 N=15이면

7+8=15

4+5+6=15

1+2+3+4+5=15

와 같이 총 3가지의 경우가 존재한다.

* 입력

첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어집니다.

* 출력

첫 줄에 총 경우수를 출력합니다.

▷ 입력 예시

15

▷ 출력 예시

3

▷ 풀이

1. 이중 for문

import java.util.Scanner;

public class Main {	
    public int solution(int n){
      int answer = 0;

      for(int i=1; i<n; i++) {
        int sum = 0;
        for(int j=i; i<n; j++) { 
          sum += j;
          if(n < sum){
            break;
          } else if(n == sum){
            answer++;
            break;
          }
        }
      }

      return answer;
    } 

    public static void main(String[] args){
        Main main = new Main();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();

        System.out.println(main.solution(n));
      }
  }

2. 포인터

import java.util.Scanner;

public class Main {	
    public int solution(int n){
      int answer = 0, sum = 0, lt = 0;
      int m = n/2+1;
      int[] arr = new int[m];

      for(int i=0; i<m; i++){
        arr[i] = i+1;
      }

      for(int rt=0; rt<m; rt++){
        sum += arr[rt];
        if(sum == n){
          answer++;
        }
        while(sum >= n){
          sum -= arr[lt++];
          if(sum == n){
            answer++;
          }
        }
      }

      for(int i=1; i<n; i++) {
        int sum = 0;
        for(int j=i; i<n; j++) { 
          sum += j;
          if(n < sum){
            break;
          } else if(n == sum){
            answer++;
            break;
          }
        }
      }

      return answer;
    } 

    public static void main(String[] args){
        Main main = new Main();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();

        System.out.println(main.solution(n));
      }
  }

▷ 핵심 포인트

1. 포인터를 사용하는 풀이는 자주 사용되므로 익숙해지면 활용도가 높습니다.