[백준] 2018번 : 수들의 합 5 (JAVA)

🔗 문제 링크

https://www.acmicpc.net/problem/2018

---

📌 문제 개요

자연수 N이 주어졌을 때, 연속된 자연수의 합으로 N을 표현할 수 있는 경우의 수를 구하는 문제

예를 들어 N = 15일 경우

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

 

총 4가지 경우가 존재한다.

---

📌 접근 방법

연속된 자연수의 합 문제이므로 투 포인터(Two Pointer) 방식으로 해결

두 개의 포인터를 사용한다.

• start : 연속 구간의 시작 값
• end : 연속 구간의 끝 값
• sum : 현재 구간의 합

초기 상태

start = 1  
end = 1  
sum = 1

 

이후 sum과 N을 비교하면서 포인터를 이동시켜 모든 연속 구간을 탐색

---

📌 핵심 아이디어

현재 구간 [start ~ end] 의 합을 유지하면서 탐색한다.

 

1️⃣ sum < N

합이 부족하므로 구간을 확장한다.

end++  
sum += end

---

2️⃣ sum > N

합이 크므로 구간을 축소한다.

sum -= start  
start++

---

3️⃣ sum == N

result++  
sum -= start  
start++

 

정답을 카운트한 뒤 다음 구간을 찾기 위해 start를 이동한다.
투 포인터는 start와 end가 한 방향으로만 이동하기 때문에 모든 연속 구간을 O(N) 시간에 탐색할 수 있다.

---

📌 전체 코드

package no_2018;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class No2018 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int start = 1;
        int end = 1;
        int sum = 1;
        int result = 0;

        while (start <= N) {

            if (sum == N) {
                result++;
                sum -= start;
                start++;
            }
            else if (sum < N) {
                end++;
                sum += end;
            }
            else {
                sum -= start;
                start++;
            }
        }

        System.out.println(result);
    }
}

---

정리

이 문제는 연속된 자연수의 합을 찾는 문제로, 투 포인터 알고리즘을 활용하면 효율적으로 해결할 수 있다.
투 포인터 방식은 다음 특징을 가진다.

• 연속 구간 문제에 적합
• 포인터가 한 방향으로만 이동
• 시간 복잡도 O(N)