섹션 3 투 포인터 & 슬라이딩 윈도우 - 5. 연속된 자연수의 합(투 포인터)

📌 문제 설명

양의 정수 N이 입력되면, 2개 이상의 연속된 자연수의 합으로 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요. 예를 들어 N=15일 때 총 3가지 방법이 존재합니다.

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

---

📝 입력 & 출력

입력

• 첫째 줄에 양의 정수 N (7 ≤ N < 1000)이 주어집니다.

출력

• 첫 줄에 연속된 자연수의 합으로 N을 표현하는 경우의 수 출력

---

🔸 예제 입력 & 출력

예제 입력 1

15

 

예제 출력 1

3

---

💡 해결 방법

• 투 포인터 (Two Pointers) 기법을 활용하여, 연속된 자연수의 구간을 왼쪽 포인터(lt)와 오른쪽 포인터(rt)로 설정하고, 그 구간의 합이 N과 같은 경우를 찾습니다.
• rt는 1부터 시작해 N/2 + 1까지 증가시키고, 합이 N 이상이면 lt를 늘려 윈도우를 줄입니다.

---

💻 코드 구현 (Java)

package partTwoPointers;

import java.util.Scanner;

public class Problem5 {
	public int solution(int n){
		int result = 0, sum = 0;
		int lt = 1;
		
		for(int rt = 1; rt <= n / 2 + 1; rt++) {
			sum += rt;
			if(sum == n) result++;
			
			while(sum >= n) {
				sum -= lt++;
				if(sum == n) result++;
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		Problem5 T = new Problem5();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		System.out.print(T.solution(n));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ lt와 rt로 구간을 조절하며 합 계산

for(int rt = 1; rt <= n / 2 + 1; rt++) {
	sum += rt;
	if(sum == n) result++;

• rt는 오른쪽 끝, lt는 왼쪽 끝을 가리키며 윈도우의 합을 유지합니다.

2️⃣ 합이 n 이상이면 lt를 증가시켜 합을 줄임

while(sum >= n) {
	sum -= lt++;
	if(sum == n) result++;
}

• 부분합이 N 이상이면 윈도우 왼쪽을 줄여나갑니다.

---

⏳ 시간 복잡도 분석

• 각 포인터는 최대 N까지 한 번씩만 이동 → O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런