[백준 2018] 수들의 합 5 (Java) - 투 포인터

🚀 문제 핵심

어떤 자연수 $N$을 연속된 자연수의 합으로 나타내는 가짓수를 구하는 문제입니다.

• 제한 시간: 2초
• 데이터 범위: $N \le 10,000,000$

$N$이 무려 천만입니다. 만약 모든 구간을 탐색하는 $O(N^2)$ 브루트포스나 백트래킹을 사용한다면 100조 번의 연산이 필요하므로 절대 통과할 수 없습니다.

---

💡 해결 전략: 투 포인터 (Two Pointers)

연속된 자연수의 합을 구할 때는 포인터 두 개(start, end)를 사용하여 구간을 조절하는 투 포인터 알고리즘이 최적입니다.

1. 상태 정의:

• sum: 현재 start부터 end까지의 합
• count: $N$을 만드는 경우의 수

2. 이동 규칙:

• sum == N: 가짓수를 하나 올리고(count++), start를 오른쪽으로 밀어 다음 구간을 탐색합니다.
• sum < N: 합이 더 커져야 하므로 end를 오른쪽으로 밀어 범위를 넓힙니다.
• sum > N: 합을 줄여야 하므로 start를 오른쪽으로 밀어 범위를 좁힙니다.

이 방식은 포인터가 각각 한 번씩만 배열 끝까지 이동하므로 $O(N)$의 시간 복잡도로 해결 가능합니다.

---

💻 구현 코드 (Java)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int n = scanner.nextInt();
            
            // start, end 포인터와 현재 합 sum 초기화
            int start = 1, end = 1, sum = 1, count = 0;
            
            while (end <= n) {
                if (sum == n) {
                    count++; // 경우의 수 발견
                    sum -= start++; // start 이동 (구간 축소)
                } else if (sum < n) {
                    sum += ++end; // end 이동 (구간 확장)
                } else {
                    sum -= start++; // sum > n 인 경우, start 이동 (구간 축소)
                }
            }
            System.out.println(count);
        }
    }
}

---

🧐 설계 포인트

1. 공간 효율성: 누적 합 배열을 따로 생성하지 않고 변수 4개만 사용하여 메모리 사용량을 최소화했습니다.
2. DP/백트래킹과의 차이:
   • DP: 연속된 구간의 특성을 활용하기엔 점화식 구성이 복잡해질 수 있습니다.
   • 백트래킹: 가지치기를 잘하더라도 천만이라는 범위를 감당하기엔 깊이가 너무 깊어집니다.
   • 결론: 선형 시간($O(N)$)이 보장되는 투 포인터가 가장 합리적인 선택입니다.

---

🎯 마치며

투 포인터는 정렬된 배열이나 연속된 수열에서 구간을 다룰 때 강력한 힘을 발휘합니다. 이번 문제는 투 포인터의 가장 표준적인 형태를 보여주는 좋은 예제였습니다.