[JAVA] 백준 2018 수들의 합

문제

자연수 N을 만드는 연속된 자연수의 합으로 나타내는 가짓수 구하기

 

 

입력

정수 N

 

출력

가짓수

 

 

---

★Key point : 투 포인터

 

입력으로 주어지는 자연수 N의 범위가 <= 10,000,000 이므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다.

이런 경우 자주 사용하는 방법인 투 포인터 사용하기

 

 

<최종 CODE>

import java.io.*;
import java.util.*;

public class P2018_연속된자연수의합구하기 {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int count = 1;
		int sum = 1;
		int start = 1;
		int end = 1;
		while (end != n){
			if (sum == n) {
				count++;
				end++;
				sum = sum + end;
			}	
			else if (sum > n) {
				sum = sum -start;
				start++;
			}
			else {
				end++;
				sum = sum + end;
			}
		}
		System.out.println(count);
	}
}

 

 

 

<CODE 설명>

인덱스를 가리키는 두 개의 포인터를 활용해서 연속된 숫자의 묶음을 표현하고, n과 sum의 크기 비교에 따라
각 포인터를 이동시킨다

<투 포인터 이동 원칙>

• sum == N: end_index++; sum = sum + end_index; count++;
• sum < N: e nd_index++;  sum = sum + end_index;
• sum > N: sum = sum - start_index; start_index++;

 

 

※ 자연수 1개 입력받는 것이므로 간단하게 Scanner 사용