[백준] 2018번 - 수들의 합 5

---

문제 분석

이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 우선 문제에 주어진 시간 제한은 2초이다. 그런데 n의 최댓값은 10,000,000으로 매우 크게 잡혀 있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법은 투 포인터 이다.
연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현하고, 문제에 접근하면 된다.

---

소스 코드

# 투 포인터

N = int(input())

count = 1 # 총 개수는 1로 초기화(마지막에 N이 하나만 들어오는 경우 고려)
start = end = 1 # 시작인덱스, 종료 인덱스 모두 1로 초기화
sum = 1

while end != N:
    if sum == N:
        count += 1
        end += 1
        sum += end
    elif sum < N:
        end += 1
        sum += end
    else:
        sum -= start
        start += 1

print(count)