[Java] 백준 2018번 <수들의 합 5>

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

2018번: 수들의 합 5

 

 

---

※ 문제  설명

 

- 이 문제는 투 포인터 알고리즘 개념을 활용하여 풀 수 있는 문제이다. 

 

- 연속되는 수들의 합으로 입력한 수를 만들 수 있는 가지 수를 구하는 문제이다. 

 

---

※ 투 포인터 ?

 

- 배열이나 리스트에서 '두 개의 포인터'를 사용하여

'특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘

 

- 투 포인터의 시간복잡도는 빅오 표기법을 사용하면 O(n)이며, 

선형시간 복잡도를 가지므로 효율적인 알고리즘이다. 

---

※ 투 포인터의 수행단계

 

① 배열 또는 리스트의 시작 위치에 첫 번째 포인터와 두 번째 포인터를 설정한다.

 

② 두 포인터 사이의 구간을 조사하고 조건을 확인한다.

 

③ 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료한다.

 

④ 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동시킨다.

 

⑤ 다시 2번 단계로 돌아가 반복한다. 

---

※ 코드 구현하는 과정

 

문제를 풀기 위해 투 포인터의 이동 법칙을 정의한다. 

 

1. sum > N

- sum = sum - start; start++;

 

2. sum < N

- end++; sum = sum + end;

 

3. sum == N

- cnt++; end++; sum = sum + end;

 

---

※ 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int cnt = 1; // 처음 자신의 경우 바로 성립되므로 1로 초기화
		int start = 1;
		int end = 1;
		int sum = 1; // 시작이 1부터이므로 합도 1부터 시작
		
		while(end != n) { // 마지막 숫자가 n이 되기 전까지 반복
			if(sum == n) { // 합이 n과 같아지면 카운트한 뒤 수 이동
				cnt++;
				end++;
				sum = sum + end;
			}else if(sum > n) { // 같지 않은 경우엔 공식에 따라 수 이동
				sum = sum - start;
				start++;
			}else {
				end++;
				sum = sum + end;
			}
		}
		
		System.out.println(cnt); // 결과 출력
	}
}