백준 2018 - 수들의 합 5

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

2018번: 수들의 합 5

 

 

 

문제 

---

 

문제는 간단하다. 

N을 받아서 N을 연속된 자연수의 합으로 나타낼 수 있는지에 대한 문제이다.

 

 

 

 

 

문제 해석

---

 

여기서 주목해야할점은 N의 범위가 10,000,000까지 가능하다는 점이다.

많은 양의 범위를 빠르게 처리해야 하기 때문에 O(N)의 시간복잡도를 가지는 알고리즘을 사용해야한다. 

어떤 범위를 계속 탐지해야 하므로, 투포인터를 사용해본다.

 

 

 

 

 

 

로직

---

 

 

두개의 포인트를 둬서 포인터를 이동시키면서, 합을 구해야 한다. 

여기서 start_inedx, end_index를 만들어서 1부터 이동시키며 sum에 추가하여 판별하는 방식을 이용한다.

 

 

1. N을 입력받는다.

2. start_index,end_index,sum,count를 1로 초기화 한다. 

3. 만약 합이 N과 같다면 count를 증가시키고,  end_index를 증가시키고, sum에는 end_index가 더해진다.

4. 만약 합이 N보다 커진다면, sum에 start_index만큼을 빼고, start_index를 증가시킨다. 

5. 만약 합이 N보다 작다면, end_index를 증가시키고, sum에 end_index값을 증가시킨다.

6. count값을 출력한다.

 

여기서 중요한 점은 합이 N보다 클때는 index를 sum에서 뺀후 포인터를 이동시킨다.

왜냐하면 start_index를 증가시킨후 빼려고 하면 더해진 값이 빠지므로, 범위를 좁힐 때는 sum값을 줄인 다음 포인터를 이동시켜야한다.

반대로 합이 N보다 작을 때는 범위를 증가시키고 sum에서 인덱스값을 더해도 상관없다.

 

 

 

 

 

 

 

 

정답

---

 

import java.util.Scanner;

public class Main {
	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 if(sum < N) {
				end_index++;
				sum = sum + end_index;
			}
		}
		System.out.println(count);
	}
}