[Algorithm] 연속된 자연수의 합

연속된 자연수의 합

설명

N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.
만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15
와 같이 총 3가지의 경우가 존재한다.

입력

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

출력

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

예시 입력 1

15

예시 출력 1

3

---

해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public int solution(int n) {
        int answer=0, lt=0, sum=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++;
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(T.solution(N));
    }
}

---

삽질

public int solution(int n) {
    int answer=0, lt=0, sum=0;
    int[] arr = new int[n-1];
    for (int i=0; i<n-1; i++) arr[i] = i+1; 
    
    for (int rt=0; rt<n-1; rt++) {
        sum += arr[rt];
        if (sum == n) answer++;
        while (sum >= n) {
            sum -= arr[lt];
            lt++;
            if (sum == n) answer++;
        }
    }
    return answer;
}

• 정답은 맞지만, 배열의 범위를 크게 잡아줄 필요가 없었다