백준 2018 수들의 합 5: 투 포인터 Python 풀이

기존 글 제목에는 백준 2108번이라고 적혀 있었지만, 본문과 코드는 2018번 ‘수들의 합 5’를 다루고 있었다. 2108번 ‘통계학’과는 다른 문제이므로 번호부터 바로잡는다.

백준 2018번은 자연수 N을 하나 이상의 연속된 자연수의 합으로 나타내는 방법의 수를 구한다. N = 15라면 답은 다음 네 가지다.

15
7 + 8
4 + 5 + 6
1 + 2 + 3 + 4 + 5

• 백준 2018번 문제

핵심은 연속 구간의 합이다

연속된 자연수 구간을 [left, right)로 두고 합을 유지한다. right가 가리키는 수는 아직 구간에 포함되지 않은 상태다.

• 현재 합이 N보다 작으면 오른쪽에 수 하나를 추가한다.
• 현재 합이 N보다 크거나 같으면 정답 여부를 확인한 뒤 왼쪽 수를 뺀다.
• 합이 정확히 N이면 count를 하나 늘린다.

모든 수가 양수이므로 오른쪽을 늘리면 합이 커지고, 왼쪽을 줄이면 합이 작아진다. 이 단조성 덕분에 이미 지나간 시작점을 다시 볼 필요가 없다.

Python 코드

import sys


read = sys.stdin.buffer.readline
n = int(read())

left = 1
right = 1
current_sum = 0
count = 0

while left <= n:
    if current_sum < n:
        current_sum += right
        right += 1
    else:
        if current_sum == n:
            count += 1

        current_sum -= left
        left += 1

print(count)

초기 window는 비어 있고 합은 0이다. 합이 작을 때 right를 더한 뒤 한 칸 이동하고, 합이 충분히 커졌을 때 left를 빼고 이동한다.

N 하나만 사용하는 경우도 자연스럽게 계산된다. 예를 들어 N = 15에서 마지막에는 window [15, 16)의 합 15를 세고 종료한다.

N이 15일 때 움직임

모든 중간 상태를 나열할 필요는 없지만 방향을 보면 이해가 쉽다.

1. 1 + 2 + 3 + 4 + 5 = 15가 되면 count를 늘린다.
2. left의 1을 빼면 합이 14가 되고, 다시 오른쪽 수를 추가한다.
3. 합이 15보다 커지면 왼쪽 수를 차례로 빼며 window를 줄인다.
4. 같은 방식으로 4 + 5 + 6, 7 + 8, 15를 찾는다.

두 pointer는 뒤로 가지 않는다. left와 right가 각각 최대 N 부근까지 한 번씩 이동한다.

복잡도

각 pointer가 증가만 하므로 시간 복잡도는 O(N)이다. 합과 pointer, count만 저장하므로 추가 공간은 O(1)이다.

원문의 분모를 바꿔 가며 등차수열 식을 검사하는 방식도 수학적으로 접근할 수 있지만, floating-point .5 판정은 필요하지 않다. 이 문제에서는 양수 연속 구간이라는 조건이 뚜렷해 투 포인터가 구현과 검증 모두 단순하다.

자주 틀리는 지점

마지막의 N 하나를 빠뜨리기

연속된 자연수는 두 개 이상이라는 조건이 없다. N 자체도 항상 한 가지 표현이므로 세어야 한다.

합이 같을 때 pointer를 움직이지 않기

정답을 찾은 뒤에도 window를 줄이거나 늘려야 한다. 그대로 두면 같은 상태에서 무한 loop가 생긴다.

자연수 범위를 0부터 시작하기

이 문제의 수열은 1부터 시작한다. 0을 포함하면 중복 표현처럼 보이는 잘못된 window가 생긴다.

서로 다른 정렬 배열에서 두 pointer를 좁혀 가는 유형은 백준 3273 두 수의 합에서 비교할 수 있다. 입력량이 많은 문제의 선택 기준은 Python input()과 readline() 비교에 정리했다.

검증 메모

코드는 N = 15의 결과 4를 확인하고, 작은 N 범위에서 모든 연속 구간을 직접 세는 brute-force 결과와 대조했다. 2026년 8월 2일 현재 백준 문제 URL은 문제 본문 대신 서비스 준비 안내를 표시해 현행 채점 제출은 확인하지 못했다.

참고 자료

• 백준 2018번 문제