2018 수들의 합5

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	32 MB	7036	3173	2482	49.217%

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

예제 입력 1

15

예제 출력 1

4

---

풀이 과정

투포인터 알고리즘을 활용해 풀었다.

1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키게 한다.
2. 현재 부분 합이 n이면 count 증가, start 증가
3. 현재 부분 합이 n보다 크면 start 증가
4. 현재 부분 합이 n보다 작으면 end 증가
5. 2~4번 반복

예를 들어 n = 5 이면

다음과 같이 동작해서 답이 2가 된다.

---

코드

import math

n = int(input())
end = 0
sum = 0
count = 0

    
for start in range(0, n):
    while sum < n and end < n :
        sum += end+1
        end += 1
    if sum == n:
        count += 1
    sum -= start+1
print(count)