연속된 자연수의 합

22 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

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

해결방법

• 기본적으로 rt를 증가시키는 구조 > 비교 ? > 작으면 rt증가, 크거나 같으면 lt 증가 후, 합에서 뺌.

  

코드

import java.util.*;

class Main {
    public int solution(int n) {
        int answer = 0, sum = 0;
        // 합으로 이루어지는 자연수 케이스는 2로 나눈것보다 클 수 없기 때문에
        // 자연수 배열을 나누기 2 + 1 로 정의하고 시작한다.
        int m = n / 2 + 1;
        int[] arr = new int[m];
        // 자연수 배열 생성
        for (int i = 0; i < m; i++) arr[i] = i + 1;
        int lt = 0;
        // 포인터 2개를 생성하여 사용한다. 
        for (int rt = 0; rt < m; rt++) {
            // rt 포인터부터 시작해서 계속 더하다가
            sum += arr[rt];
            // 정답 케이스가 발견되면 +1
            if (sum == n) answer++;
            // 이후, 더하다가 합이 15보다 같거나 큰 경우, lt 포인터가 가리키는
            // 원소부터 뺀다. 빼다가 합이 15인 케이스가 나오면 정답을 증가시킨다.
            while (sum >= n) {
                sum -= arr[lt++];
                if (sum == n) answer++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main.Main T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        System.out.print(T.solution(n));
    }
}