[Inflearn] 자바 알고리즘 문제풀이 #03-05 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)이 주어집니다.

 

출력 

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

 

 

 

내 풀이

import java.util.Scanner;

public class Main3_5 {
    public int Solution(int n) {
        int num, sum, answer=0;
        for (int i = 1; i < n/2+1; i++) {
            sum = 0;
            num = i;
            while(sum<n) {
                sum += num++;
                if(sum==n) answer++;
            }
        }
        return answer;
    }

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

배열, 투포인터 안쓰고 할 수 있는 방법을 생각하다 완성함 !

 

 

 

선생님 풀이 (two pointers)

import java.util.Scanner;

public class Main3_5 {
    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++;
            }
        }
        return answer;
    }

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

어.답.sliding window, two pointer (어차피 답은 슬라이딩 윈도우, 투포인터)

rt는 쭉쭉 더해주고 lt는 쭉쭉 빼주고. 재미있음

배열 선언 및 초기화해서 사용해도 되는군 !

 

 

선생님 풀이 (수학적 해법)

import java.util.Scanner;

public class Main3_5 {
    public int Solution(int n) {
        int answer=0, cnt=1; // cnt : 연속된 자연수의 개수
        n--;
        while (n>0) {
            cnt++;
            n = n-cnt;
            if(n%cnt==0) answer++;
        }
        return answer;
    }
    public static void main(String[] args) {
        Main3_5 T = new Main3_5();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(T.Solution(n));
    }
}

 

 

 

결과