[프로그래머스] Level 2 숫자의 표현

문제 링크

programmers.co.kr/learn/courses/30/lessons/12924

풀이 1

$n$을 $k$개의 연속된 자연수의 합으로 나타낼 수 있는지 확인하려면 어떻게 해야할까?
차근차근 따져보도록 하자.

$k$가 1이라면 $n$ 자기 자신으로 표현된다.

$k$가 2라면 어떤 자연수 $m$과 $m+1$에 대해서 $n=m+m+1$이 성립해야 한다.
이는 $n$에서 1을 빼고 2로 나누어 떨어지는지 확인하면 된다.

$k$가 3이라면 어떤 자연수 $m$, $m+1$, $m+2$에 대해서 $n=m+m+1+m+2$가 성립해야 한다.
이는 $n$에서 $1+2$를 빼고 3으로 나누어 떨어지는지 확인하면 된다.

규칙이 보이는가? 즉, $n$에서 1+2+...+k-1을 빼고 $k$로 나누어 떨어지는지 확인하면 되는 것이다.
이때, $m$은 0보다 커야 하므로 1+2+...+k-1의 값은 n보다 작아야 한다.

이 풀이의 시간복잡도는 $O(\sqrt{n})$이다.

C++ 코드

int solution(int n) {
    int answer = 0;
    for (int i = 1; n > 0; n -= i++)
        if (n % i == 0) ++answer;
    return answer;
}

풀이 2

사실 이 글을 쓴 목적은 풀이 2의 증명이다.
다양한 블로그에서 다음과 같은 말을 인용한다.

주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는
주어진 수의 홀수 약수의 개수와 같다라는 정수론 정리가 있습니다.

이게 왜 성립하는지는 설명하는 블로그가 잘 보이지 않아서, 증명을 찾아 보았다.

주어진 수를 $n$이라고 하자.
1부터 $a$까지 정수의 합은 다음과 같다.

$$ 1+2+...+a = \frac{a(a+1)}{2} $$
$n$을 $b+1$부터 $a$까지의 합이라고 한다면 다음과 같이 쓸 수 있다.

$$ \begin{aligned} n &= \frac{a(a+1)}{2} - \frac{b(b+1)}{2} \end{aligned} $$

양변에 2를 곱하면 다음과 같다.

$$ \begin{aligned} 2n &= (a^2+a) - (b^2+b)\\ &= (a^2-b^2)+(a-b)\\ &= (a-b)(a+b+1) \end{aligned} $$

$(a+b+1) - (a-b) = 2b+1$이므로 $a+b+1$과 $a-b$는 서로 다른 패리티를 갖는다.
서로 다른 패리티를 갖는다는 말은 어느 한쪽이 홀수라면 다른 한쪽은 짝수라는 뜻이다.

정리해보자.
$n$이 $b+1$부터 $a$까지의 합이라면 어떤 홀수 $p$와 짝수 $q$가 존재하여 $2n = pq$로 표현이 가능해진다.
이때, $p$가 $2n$의 약수라면 $p$는 $n$의 약수이기도 하다.

따라서, $n$을 연속된 자연수의 합으로 표현하는 방법의 수는 $n$의 홀수 약수의 개수와 같다.

이 풀이의 시간복잡도는 $O(n)$이다.
(물론, 반복문의 i를 $\sqrt{n}$까지 순회하면서 i와 n/i를 동시에 보는 식으로 $O(\sqrt{n})$도 가능하다)

C++ 코드

int solution(int n) {
    int answer = 0;
    for (int i = 1; i <= n; i += 2)
        if (n % i == 0) ++answer;
    return answer;
}

보면 좋을 문서들

math.stackexchange.com/questions/1636288/how-to-find-total-number-of-sum-of-consecutive-number-of-n/1636315

math.stackexchange.com/questions/1100897/sum-of-consecutive-numbers