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

설명

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

 

 

내 풀이

 

https://better21.tistory.com/147

[투포인터] 연속 부분수열 .java

 

위에서 푼 문제와 비슷하여 금방 구현했다

이해하기 쉽게 lt, rt로 변수명을 바꿨다

 

정수 n은 정답에 들어가서는 안되기 때문에 배열 크기를 n-1로 하여 n이 15일 때 배열의 마지막 원소가 14가 되게 하였

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n-1];
        for(int i = 0; i < n-1; i++){
            arr[i] = i+1;
        }

        int answer = 0;
        int lt = 0;
        int sum = 0;

        for(int rt = 0; rt < n-1; rt++){
            sum += arr[rt];
            while(sum > n){
                sum -= arr[lt++];

            }
            if(sum == n) answer++;
        }

        System.out.println(answer);

    }
}

 

 

다른 풀이 - 투 포인터

예에서 15 / 2 = 7이다 이에 1을 더한 8이 마지막 경우의 수임을 이용한 것이다

-> arr 배열의 값과 for문도 n / 2 + 1한 값까지로 구현

 

import java.util.Scanner;

public class Main {
    public int solution(int n){
        int answer = 0;
        int sum = 0;
        int 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 < (n/2 + 1); 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) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        System.out.println(T.solution(n));

    }
}

 

 

다른 풀이 - 수학

 

연속된 자연수의 개수에 따라 1씩 차이나도록 가장 작은 값으로 먼저 배분
-> 남은 값을 동일하게 배분
=> 연속된 자연수가 존재

 

 

 

cnt = 연속된 자연수 개수

-> 처음에 1을 빼야하기에 while문 전에 처리

 

n이 0이 되면 가능한 연속된 자연수의 개수가 없다는 것

 

import java.util.Scanner;

public class Main {
    public int solution(int n){
        int answer = 0;
        int cnt = 1;
        n--;//1 먼저 뺌
        while(n > 0){
            cnt++;
            n -= cnt;
            if(n % cnt == 0) 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.println(T.solution(n));

    }
}

💡💡

크기가 작아서 아무 생각 없이 n-1까지로 설정해서 성공했지만 다른 문제에서 엄청 큰 값이 들어오면 시간 초과가 날 수 있다

=> 최대한 적은 개수를 검사하도록 구현해야 한다

수학적으로 푼 풀이를 보고 수학을 이래서 배워야하는구나를 알았다 너무 간단한 코드로 구현해서 놀랐다