[백준/Java] 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이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오. 

 

 

- 문제 풀이 방식

 투 포인터 방식을 사용한다. 

'연속된 수'의 합을 구해야 하므로 시작 값(start)과 끝 값(end)을 투 포인터로 설정한다. 

투 포인터 이동 원칙을 활용한다. 

 

1. sum > N 인 경우

  합이 N보다 크기 때문에 범위를 줄여줘야 한다. 

  -> 1) sum = sum - start  2) start++

 

2. sum < N 인 경우

 합이 N보다 작기 때문에 범위를 확장해야 한다. 

 -> 1) end++  2) sum = sum + end

 

3. sum == N 인 경우

 가짓수를 늘려준다. 확장시켜준다.

 -> 1) cnt++  2) end++

 

 

- 코드

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int start = 1, end = 1;
		int sum = 1, cnt = 1;
		
		while (end != N) {
			if (sum > N) {
				sum -= start;
				start++;
			}
			else if (sum < N) {
				end++;
				sum += end;
			}
			else {
				cnt++;
				end++;
				sum += end;
			}
		}
		
		System.out.println(cnt);
		
		sc.close();
	}

}

 

 

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

2018번: 수들의 합 5