연속된 자연수의 합(two pointers + 수학)

5. 연속된 자연수의 합

설명

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

📌 1번 방법( two pointers)

연속된 자연수의 합이니까 n/2 + 1보다 큰 값은 올 수가 없음

15면 7+1이 8이고 8,9면 당연히 오버

import java.util.*;
import java.util.Scanner;

class Main {
    public int solution(int n) {
        int answer = 0, sum = 0, lt = 0;
        //연속된 자연수니까 m / 2보다 큰 값이 올수가 없음!! ex) 15면 7+1이 8이고 8만끼리만 더해도 16인데 어떻게 그 이상이 오겠음
        int m = n / 2 + 1;
        //인덱스 0부터니까 인덱스 m-1 까지 슉 돌리겠지
        int[] arr = new int[m];
        //이때 i번쨰를 그냥 i+1로해서 아예 인덱스 0번이 1부터 시작하게하면 m까지 다돌겠지
        for (int i = 0; i < m; i++) {
            arr[i] = i + 1;
            sum += arr[i];
            if (sum == n) {
                answer++;
            }
            //앞에 문제와 동일한 원리
            while (sum >= n) {
                sum -= arr[lt++];
                if (sum == n) {
                    answer++;
                }
            }

        }
        return answer;
    }

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

📌 2번 방법(수학적 방법 )

:n에서 연속된 자연수의 합을 빼고 연속된 자연수의 갯수로 나눴을 때 나머지가 0이면

해당 (자연수+몫)들의 합이 n인 것을 이용!

import java.util.*;
import java.util.Scanner;

class Main {
    public int solution(int n) {
        //cnt는 연속된 자연수의 갯수
        int answer = 0, cnt = 1;
        n--; //시작부터 n 일단 빼고 (자연수 1부터 시작..자연수 1 빼기)
        while(n>0){
            cnt ++; // 자연수 1개 추가지만 일단 여기선 증가하는 자연수 역할도!
            n = n - cnt; // 만약 주어진 n 15라면 맨위(n--;)에서 1뺀 14..그리고 거기서 2를 뺀 12..즉 연속된 자연수 1,2를 뺀 것과 같은..
            if(n % cnt == 0){ //    12 / 2(연속된자연수갯수) = 몫 6.. 나머지 0.. 1+6과 2+6 더하면 15 !
                            // (n - 연속된 자연수의 합 )%연속된 자연수의 갯수 = 0 이면 이들의 합이 n이라는 뜻임!
                                // 연속된 자연수에 몫만큼을 각각 더하면 n이 됨.. 수학적 방법..
                answer ++;
            }
        }
        return answer;
    }

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