(4) 연속된 자연수의 합 구하기

어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1<=N<=10,000,000)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다. 이때 사용하는 자연수는 N 이여야 한다. 예를 들어 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5 이다. 반면, 10을 나타내는 방법은 10, 1+2+3+4이다. N을 입력받아 연속된 자연수의 합으로 나타내는 가짓수를 출력하는 프로그램을 작성하시오.

 

입력

1번째 줄에 정수 N이 주어진다.

 

출력

입력된 자연수 N을 연속된 자연수의 합으로 나타내는 가짓수를 출력한다.

 

예제 입력 1

15 // N

 

예제 출력 1

4

 

코드

import java.util.Scanner;

public class P2018_연속된자연수의합 {
	
	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int count = 1;
		int start_index = 1;
		int end_index = 1;
		int sum = 1;
		
		while(end_index != N) {
			
			if(sum == N){
				count++;
				end_index++;
				sum = sum + end_index;
			
			} else if(sum > N){
				sum = sum - start_index;
				start_index++;
			
			} else {
				end_index++;
				sum = sum + end_index;
			}
			
		}
		System.out.println(count);
		
	}
}

 

투 포인터 이동 원칙을 이용해서 접근하면 되는 문제이다.

1~15 을 1번째부터 start_index, end_index 로 시작하고, sum 이 15가 될 때까지 end_index 를 이동시키고, 15가 되는 경우 start_index를 이동한다.

start_index -->
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
end_index -->

 

투 포인터 이동 원칙

sum > N : sum = sum - start_index; start_index++;

sum < N : end_index++; sum = sum + end_index;

sum == N : end_index++; sum = sum + end_index; count++;

 

---

Reference

백준의 올라인 저지 2018번