자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)] : 연속된 자연수의 합 2 (수학적으로 푸는 방법)

 

https://hyejin.tistory.com/1224

자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)] : 연속된 자연

-> 이전 풀이에서 이어집니다. 

 

 

 

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

public int solution3(int n) {
    int answer = 0, cnt = 1; // cnt는 연속된 수의 개수 
    n--;
    while (n > 0) {
        cnt++;
        n = n - cnt;
        if (n % cnt == 0) answer++;
    }

    return answer;
}

👾 : 기존에 문제 풀때는 슬라이딩 윈도우 방법을 사용했더라면 이번에는 수학적 방법을 사용해서 문제를 푸는 방법을 설명한다. 

연속된 수라고 했으니 먼저 2개의 수를 더해서 15가 되는 게 있는지 찾아본다. 

1 2 이렇게 두 개의 수를 15에서 빼고 그 다음 연속된 수의 개수 2를 나눠서 0이 되면 연속된 두개의 자연수의 합이 15가 되는 게 있다는 말이다. 

1️⃣ 2️⃣ -> 7 + 8 이 있으므로 answer 에 + 1 해준다. 

 

다음 세자리 연속된 자연수의 합으로 15가 되는 수가 있는지 확인해본다면 

1️⃣ 2️⃣ 3️⃣ 

15에서 - 1 - 2 - 3 을 하고  = 9 , 그 다음 3을 나눴을 때 나눠 떨어진다면 역시 연속된 3개의 자연수의 합이 15가 되는 게 있다는 말이므로 

answer 에 + 1 을 해준다.  ( 4 + 5 + 6 ) 

 

다음 4자리 연속된 자연수의 합으로 15가 되는 수 가 있는지 확인해본다면 

1️⃣ 2️⃣ 3️⃣ 4️⃣ 

15 에서 - 1 - 2 - 3 - 4 을 하고 = 5, 그 다음 4로 나눴을 때 나눠 떨어지지 않기 때문에 연속된 4개의 자연수의 합이 15가 되는 것은 없다는 뜻이다. 

 

다음 5자리 연속된 자연수의 합으로 15다 되는 수가 있는지 확인해본다면 

1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣ 

15 에서 15를 빼면 0이기 때문에 0 에서 5를 나누면 0이므로 연속된 자연수의 합이 15가 된다는 것이다. 

 

이런식으로 수학적 방식으로 접근해서 문제를 풀 수 도 있다는 것이다.