섹션 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

---

💡 해결 방법

• 연속된 자연수의 합으로 N을 표현하는 경우를 찾기 위해 작은 수부터 차례대로 더해가며 나머지를 확인하는 방식입니다.
• 예를 들어 k개의 연속된 수의 합이 N이 되려면, N에서 1부터 (k-1)까지의 누적합을 빼고, 그 결과가 k로 나누어 떨어지는지를 확인합니다.
• 예: N = 15일 때,
  • k = 2 → 15 - 1 = 14 → 14 % 2 == 0 → 가능 (7+8)
  • k = 3 → 15 - 1 - 2 = 12 → 12 % 3 == 0 → 가능 (4+5+6)
  • k = 4 → 15 - 1 - 2 - 3 = 9 → 9 % 4 != 0 → 불가능
  • ...
• 핵심 아이디어: N에서 누적합을 계속 빼가며 k로 나누어떨어지는지 확인

---

💻 코드 구현 (Java)

package partTwoPointers;

import java.util.Scanner;

public class Problem5_1 {
	public int solution(int n) {
		int result = 0, cnt = 1;
		n--;
		while(n > 0) {
			n -= ++cnt;
			if(n % cnt == 0) result++;
		}
		return result;
	}

	public static void main(String[] args) {
		Problem5_1 T = new Problem5_1();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		System.out.print(T.solution(n));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 기본 아이디어

• 연속된 자연수의 합이 N이 되는 방법을 찾기 위해, cnt개의 수로 분할할 수 있는지 확인합니다.

2️⃣ while문 로직

n--;
while(n > 0) {
	n -= ++cnt;
	if(n % cnt == 0) result++;
}

• n--는 첫 항을 제외한 누적합 비교를 위한 초기 세팅입니다.
• cnt를 2부터 증가시키면서 누적합을 빼줍니다.
• 뺀 결과가 cnt로 나누어떨어지면 → 연속된 수 존재

---

⏳ 시간 복잡도 분석

• cnt가 증가하면서 누적합도 커지므로 반복 횟수는 약 O(√N) 이하입니다.

---

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

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