Consecutive Numbers Sum

Consecutive Numbers Sum

 

문제 내용

주어진 숫자(N)보다 같거나 낮은 수의 연속적인 배열의 Sum이 주어진 숫자와 같은 경우의 수는 몇개인가?

 

접근 방법

수학적인 접근을 통해서 문제를 해결해야 한다.

만약에 15라는 N이 주어졌다고 생각해 보겠다.

15(N) = 4 + 5 + 6 으로 이루어 질 수 있다.

또는

15(N) = 8 + 7 로도 이루어 질 수 있다.

이것을 일반항화 시키면 다음과 같다.

N = (x + 1) + (x + 2) + (x+ 3) + ... + (x + k)

여기서 k는 연속된 갯수이다.

8 + 7은 두개의 연속된 갯수 임으로 k는 2이다.

 이를 x로 묶어 보겠다.

N = x*k + (0 + 1) + (0 + 2) + (0+ 3) + ... + (0 + k)

여기서 다시 한번 더 일반화 시켜보겠다.

N = x*k + ((k + 1) * k) /2 

이 식을 말로 풀자면 다음과 같이 말을 할 수 있다.

k 의 갯수가 1이라면

N = x + 1

이것을 15에 대입해보면 아래와 같이 표현할 수 있다.

15(N) = 14(x) +1(k)

본 문제는 자기 자신도 하나의 Consecutive Numbers로 인정 하고 있다.

그럼 k를 5로 만들어 보면 어떻게 될까?

(5+1) * 5 / 2 = 15가 된다. 이때 x는 반듯이 0이 될 수 밖에 없다.

이것을 기본으로 해서

• k의 증가 범위는 x를 0으로 놓았을 때 그 합이 N을 초과 하면 안된다.

이것을 최적화 식으로 더 깊게 들어가면

• k≤ 2N+ 1/4​​−1/2 (Solution 참고)

가 되는데 이를 추측해 내기에는 시간이 부족 함으로  ​

• (k + 1) * k / 2 <= N

으로 사용하겠다.

이제 마지막으로 

N = x*k + ((k + 1) * k) /2 

이 식을 변경해 보겠다.

N - ((k + 1) * k) / 2 = x*k 

이 식을 말로 풀어서 설명하자면 다음과 같다.

1부터 k까지의 Sum을 뺀 N의 나머지는 k의 횟수곱으로 표현 되어야 한다.

15(N) = 8 + 7

을 예로 들어 보자면 다음과 같이 볼 수 있다.

15 = 6*2 + (0 + 1) + (0 + 2)

15 - 3 = 6 * 2

12 = 12

즉 연속더하기가 된 횟수로 나머지를 나누었을 때 x는 해당 횟수로 딱 떨어져야지만 된다.

위의 예를 보면 6이 2개이고 2개의 연속수 Sum으로 이루어 졌기 때문에 본 문제에 답중 하나로 부합하다고 볼 수 있다.

이를 코드로 표현하면 아래와 같다.

이렇게 부합되는 모든 경우의 수를 찾으면 된다.

class Solution {
    public int consecutiveNumbersSum(int N) {
        int result = 0;
        for(int k = 2; ((k*(k+1))/2) <= N; k++){
            if((N - ((k*(k+1))/2)) % k == 0) result++;
        }
        return result + 1;
    }
}

시간 복잡도는 O(root N) 이다.

소수의 갯수가 N의 루트를 넘지 못하는 사유라고 한다. 다들 너무 당연하게 말하니 공부 잘 못한 내 잘못 이겠지...

이런 문제 잘 푸는 사람들 보면.. 수학 잘하는 사람 부럽다 ㅠㅠ