연속된 자연수의 합

연속된 자연수의 합

어떤 수 $n$을 연속된 자연수의 합으로 표현할 수 있는 개수를 구하는 문제입니다. 예를 들어 15의 경우

로 나타낼 수 있습니다.

투 포인터

이 문제는 투 포인터로 풀 수 있습니다. $start$와 $end$를 증가시키거나 낮추는 방식으로 문제를 풀 수 있습니다. 다음과 같은 로직을 적용합니다.

sum = start 부터 end 까지의 합
cnt = 개수
if sum < n:
	end += 1 # end 를 한 칸 더 늘려줌으로써 다음 자연수까지 포함
elif sum > n:
	start += 1 # start 를 한 칸 당김으로써 이전 자연수를 제거
else:
	cnt += 1
	end += 1 # 또 다른 합을 찾기 위해 end를 한칸 늘려줌

Python 코드

import sys

input = sys.stdin.readline
n = int(input())
start, end, cnt, sum = 1, 1, 0, 0

while end <= n:
    if sum < n:
        end += 1
    elif sum > n:
        start += 1
    else:
        cnt += 1
        end += 1

    sum = (end * (end + 1)) // 2 - ((start-1) * start) // 2 # start ~ end의 합

print(cnt)

수학적 풀이

위의 표를 보면 연속된 자연수의 합에서, 1부터 시작하는 최솟값은 고정되어있고, 그 뒤로는 연속된 숫자의 개수에 따라 증가하는 것을 찾을 수 있습니다. 따라서, 다음과 같은 결과를 도출해 낼 수 있습니다.

연속된 숫자의 개수 n에 따른 첫번째 값(1부터 n까지의 합)을 뺀 값이 n으로 나누어 떨어진다면 n개의 연속된 자연수의 합으로 표현할 수 있다.

Python 코드

import sys

input = sys.stdin.readline
n = int(input())

cnt = 0
for i in range(1, n + 1):
    base = (i * (i + 1)) // 2
    if base > n:
        break
    if (n - base) % i == 0:
        cnt += 1

print(cnt)