[Java | Algorithm] 연속된 자연수의 합 - 수학적풀이

lt와 rt로 2개의 pointer 개념을 이용한 문제풀이 방법은 이해가 됐지만 이런 수학적 풀이는 금방 까먹을게 뻔하기 때문에 (나 자신은 내가 잘 안다) 기록해두려 한다 ~.~

---

설명

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

---

해당 방법은 n을 연속된 숫자 합이 몇개로(자릿수로) 표현할 지에 중점을 둔다.

 

예를 들어 n이 15일 때 n을 2개의 연속된 합 숫자로 표현하기 위해선 자릿수(cnt)를 2로 두는 것이다. ( 15 = 7+8 )

진행 순서는 아래와 같다.

1. 15(n) - 1 - 2 = 12
2. 12 % 2(cnt) 가 0일 때 => 15는 2개의 연속된 숫자 합으로 표현 가능
   • 1 + 2에 12/2의 몫 6을 각각 분배해준다면
   • 7 + 8이 되고 이는 n값인 15와 같다

 

n이 15이고 n을 3개의 연속된 합 숫자로 표현할 때는 cnt를 3으로 맞춰두고 진행하면 된다. ( 15 = 4 + 5 + 6 )

1. 15(n) - 1 - 2 - 3 = 9
2. 9 % 3(cnt) == 0 이므로 answer++;
   • 1 + 2 + 3에 9/3의 몫 3을 각각 분배해줄 때 
   • 4 + 5 + 6 = 15 로 n값인 15와 같아진다.

 

만약, n이 15이고 n을 4개의 연속된 합 숫자로 표현할 때는 cnt를 4로 맞춰두고 진행하면 된다. ( 15는 4개의 연속된 수로 표현할 수 없다 )

1. 15(n) - 1 - 2 - 3 - 4 = 5
2. 5 % 4(cnt) 가 0이 아닐 때 => 15는 4개의 연속된 숫자 합으로 표현 불가능

 

즉, 자릿수만큼 연속된 숫자(cnt가 3이면 1, 2, 3)를 n에서 뺀 값을 자릿수와 % 연산했을 때 결과값이 0일 때(= 나누어 떨어질 때) cnt만큼 연속된 숫자합으로 n을 표현할 수 있다는 것이다.

 

package inflearn.TwopointersANDSlidingwindow;

import java.util.Scanner;

// 3-5. 연속된 자연수의 합(two pointers) + (수학)
public class Twopointers3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] arr = new int[n/2+1];  // 연속된 자연수의 합중에 가장 큰 숫자는 n/2+1 이므로
        for(int i=0; i<n/2+1; i++) arr[i] = i+1;

        Twopointers3 twopointers3 = new Twopointers3();
        System.out.println(twopointers3.solution(n, arr));
        System.out.println(twopointers3.solution2(n));
    }

    // 수학적 방법
    public int solution2(int n){
        int answer = 0, cnt=1;
        n -= cnt;

        while(n>0){
            cnt++; // 자릿수 증가
            n -= cnt; // cnt가 연속된 자연수의갯수
            if(n % cnt == 0) answer++; // 0%cnt도 0이므로 정답으로 카운팅된다.
        }

        return answer;
    }

    // two pointers 방법
    public int solution(int n, int[] arr){
        int answer = 0;
        int lt = 0, sum = 0;

        // lt와 rt로 연속된 수열을 구하는 문제
        for(int rt=0; rt<arr.length; rt++){

            sum += arr[rt];
            while (sum > n){ // sum이 n보다 커진다면 lt값을 빼면서 lt를 증가시키며 n값과 작아질때 까지 반복 ( n값과 같으면 if문에 걸려서 answer count )
                sum -= arr[lt++];
            }
            if(sum == n) answer++;

        }
        return answer;
    }
}