[백준_2018번] 수들의 합 5

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

2018번: 수들의 합 5

[문제]

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

[입력 조건]

• 첫 줄에 정수 N이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_2018 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] num=new int[n];
		
		int start=0,end=0;
		int sum=0;
		int result=0;
		
		while(start<=n) {
			// end 포인터 증가 -> 합계가 늘어남
			while(++end<=n) {
				sum+=end;
				
				if(sum==n) // 정답을 만족하는 경우
					result++;
				if(sum>n) // n을 넘어서면 end 포인터 증가 중지
					break;
			}
			
			// start 포인터 감소 -> 합계가 줄어듬
			while(++start<=n) {
				sum-=start;
				
				if(sum==n) // 정답을 만족하는 경우
					result++;
				if(sum<n) // n보다 부족하면 start 포인터 감소 중지
					break;
			}
		}
		
		System.out.println(result);
	}

}

 

[고찰]

 이번 문제는 투포인터 유형이였다. 투포인터나 슬라이딩 윈도우 쪽이 부족한 것 같아 쉬운 예제부터 몇 개씩 풀어보는 중이다.