[투 포인터] 5. 연속된 자연수의 합

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

 

 

<<풀이>>

 

시간 복잡도 : O(N)

풀이 방법 : 투포인터, 슬라이딩 윈도우

 

우선 나는 투포인터와 슬라이딩 윈도우를 복합적으로 이용하여 구했다.

사실, 이전 강의의 코드와 크게 차이가 없어서 금방했다.

강사님의 또 다른 풀이가 있을 거 같아 기대가 된다 ㅋㅋ

import java.util.*;

class Main {

    public int solution(int n) {
        int lt = 1, sum = 0;
        int answer = 0;
        for(int rt = 1; rt < n; rt++) {
            sum += rt;
            while (sum >= n) {
                if (sum == n) {
                    answer++;
                    sum -= lt++;
                } else if(sum > n) sum -= lt++;
            }
        }

        return answer;

    }



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

 

-강사님 풀이-

 

강사님 풀이는 두 가지가 있었는데, 하나는 나와 같았다 !! ㅎㅎ

 

근데 또 다른 방식은 완전히 수학적으로 접근한 방식인데 신박했다 ㅋㅋ..

 

이 강사님의 매력은 미쳤다 ..

 

import java.util.*;

class Main {

    public int solution(int n) {
        int answer = 0, cnt = 1;
        n--;
        while(n > 0) {
            cnt++;
            n = n - cnt;
            if(n % cnt == 0) answer++;
        }

        return answer;

    }



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

 

ㅋㅋㅋㅋ 이 코드를 보면 이해를 하겠는가!!

 

그려서 설명해보겠다.

 

ㅋㅋㅋㅋ 신기하지 않나 ?? 연속된 값의 합이 구하고자 하는 값을 구할 때 미리 연속될 갯수를 정해두고 먼저 1 부터 n 까지 합한 것을 구하려는 값에 뺀 뒤에 연속될 갯수 만큼 나눠줬을 때 나머지가 0이 되면 연속된 자연수가 가능하게 되는 것이다. 신기하면서도 신박하다 정말..

 

오늘도 한 대 맞고 두 대 맞고 간다 ㅋㅋ ㅎㅎ