투 포인터 - (1)

연속된 자연수 합 구하기

문제
어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

입력 예시
15

출력 예시
4

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
start=1
end=1
count=1
sum=1
while end!=n:
    if sum==n:
        count+=1
        end+=1
        sum+=end
    elif sum > n:
        sum-=start
        start+=1
    else:
        end+=1
        sum+=end
print(count)

start index, end index 두 개의 포인터를 이동하면서 문제를 풀어야 한다.

1,2,3,4,5,6,7,8,..15 의 배열이 있다고 해보자.
1,2,3,4 까지 sum<n 이니 end만 1씩 증가한다.

1,2,3,4,5 에서 sum==n 이니 count++ 하고
end++ 로 end=6이 된다.
그리고 sum+=end 하면 21이 된다.

그러면 sum>n 이니sum-=start 하고 start를 오른쪽으로 한 칸 이동 시켜 2,3,4,5,6 이 되도록 한다.

의외로 헷갈린다?!

이런 투 포인터 문제를 접해보지 않아서 그런지 어려웠다.
sum=0 으로 계속 초기화를 통해 앞으로 나아가려 했으나 그러면 시간복잡도가 훨씬 증가할 것으로 보인다.