문제

문제: 자연수 $n$이 주어질 때, 이를 연속된 자연수들의 합으로 표현하는 방법의 수를 구하라.
예시: $n = 15$일 때,
$1 + 2 + 3 + 4 + 5 = 15$
$4 + 5 + 6 = 15$
$7 + 8 = 15$
$15 = 15$
총 4가지 방법 존재.

풀이

완전탐색을 이용한 풀이, 투포인터를 사용한 풀이가 가능하다.

1️⃣ 완전 탐색 (Brute Force)

가장 직관적인 방법은 $1$부터 시작해서 $n$까지 각 숫자를 '시작점'으로 잡고, 숫자를 하나씩 더해가며 $n$이 되는지 확인하는 것이다.

• 1을 시작으로 하는 연속된 자연수들
• 2를 시작으로 하는 연속된 자연수들
• ...
• $n$을 시작으로 하는 연속된 자연수들

풀이 로직

1. $i$를 $1$부터 $n$까지 반복합니다 (연속된 수의 시작점).
2. $i$부터 시작해서 $i + 1, i + 2, \dots$를 차례대로 더합니다.
3. 합이 $n$과 같아지면 카운트를 1 증가시키고 다음 시작점($i+1$)으로 넘어갑니다.
4. 합이 $n$을 초과하면 더 이상 더할 필요가 없으므로 중단하고 다음 시작점으로 넘어갑니다.

💻 풀이 코드 (완전 탐색)

def solution(n):
    answer = 0
    for i in range(1, n + 1):
        total = 0
        for j in range(i, n + 1):
            total += j
            if total == n:
                answer += 1
                break
            if total > n:
                break
    return answer

---

2️⃣ 투 포인터(Two Pointers)

투 포인터는 주로 정렬된 배열에서 연속된 구간의 합을 구할 때 사용하는 알고리즘이다. 이 문제에서도 $1$부터 $n$까지의 자연수가 순서대로 나열되어 있다고 가정하고 적용할 수 있다.

투 포인터 접근법

left, right 두 포인터로 구간 [left, right]의 합을 관리한다.

• left, right를 모두 $1$로 설정하고 시작한다.
• 종료 조건 : left가 n을 넘어가면 종료한다.

조건	동작
total == n	경우의 수 +1, right 이동
total < n	right 이동 (합을 늘림)
total > n	left 이동 (합을 줄임)

💻 풀이 코드 (투포인터)

def solution(n):
    count = 0
    left, right = 1, 1
    total = 1  # 초기 구간 [1, 1]의 합

    while left <= n:
        if total == n:
            count += 1
            right += 1
            total += right   # right 확장
        elif total < n:
            right += 1
            total += right   # right 확장
        else:  # total > n
            total -= left    # left 제거
            left += 1

    return count

동작 흐름 (n = 15)

[1,1]  total=1  → right 이동
[1,2]  total=3  → right 이동
[1,3]  total=6  → right 이동
[1,4]  total=10 → right 이동
[1,5]  total=15 → ✅ count=1, right 이동
[1,6]  total=21 → left 이동
[2,6]  total=20 → left 이동
[3,6]  total=18 → left 이동
[4,6]  total=15 → ✅ count=2, right 이동
[4,7]  total=22 → left 이동
[5,7]  total=19 → left 이동
[6,7]  total=13 → right 이동
[6,8]  total=21 → left 이동
[7,8]  total=15 → ✅ count=3, right 이동
[7,9]  total=24 → left 이동
...
[15,15] total=15 → ✅ count=4

핵심 포인트

• 시간복잡도: O(n) — left, right 각각 최대 n번 이동
• 종료 조건: left > n 이 되면 더 이상 유효한 구간 없음
• right += 1 후 total += right 순서에 주의 (먼저 포인터를 옮긴 뒤 합산)
  
  

🤔 total == n 일때, 왜 right만 이동하지?

right, left둘다 이동시키거나 left만 이동시키는 방식은 안되는걸까?
결론부터 말하면 셋 다 가능하다. 다만 각각 놓치는 케이스가 없도록 처리를 다르게 해야 한다.

right만 이동하면?

total == n을 찾은 순간, left를 고정한 채 right를 늘리면 다음 상태는 total > n이 되어 자연스럽게 left가 이동한다.

[4,5,6] = 15 ✅  → right 이동
[4,5,6,7] = 22  → left 이동
[5,6,7] = 18    → left 이동
[6,7] = 13      → right 이동
[6,7,8] = 21    → left 이동
[7,8] = 15 ✅

흐름이 자연스럽게 이어져서 코드가 단순해지는 장점이 있다.

left만 이동하면?

if total == n:
    count += 1
    total -= left  # left 제거
    left += 1

이것도 동작한다. left를 줄이면 total < n이 되어 right가 자연스럽게 이동한다.

[4,5,6] = 15 ✅  → left 이동
[5,6] = 11       → right 이동
[5,6,7] = 18     → left 이동
[6,7] = 13       → right 이동
[6,7,8] = 21     → left 이동
[7,8] = 15 ✅

left, right 둘 다 이동하면?

if total == n:
    count += 1
    total -= left  # left 제거 후
    left += 1
    right += 1     # right도 추가
    total += right

이것도 가능하다. 단, 반드시 두 줄을 같이 써야 하고, 순서도 지켜야 해서 실수하기 쉽다.