백준 2018번(수들의 합 5)[JAVA]

풀이

n이 최악의 경우 10,000,000까지 커지므로, O(N)인 알고리즘을 사용해서 풀어야한다.
이런 경우 투 포인트 개념을 도입하여 풀 수 있다. 즉, 시작 인덱스 포인터와 끝 인덱스 포인터, 이 2개의 포인터를 가지고 배열을 탐색하는 것이다. 그러면 배열을 한 바퀴 돌 때(O(N)의 시간 복잡도) 이 문제에서 원하는 모든 계산을 할 수 있다.
이 포인터 2개 움직임의 기준은 시작 포인터의 값부터 끝 포인터의 값까지 더한 값(변수 : sum)이다.

• 이 변수 sum을 기준으로 sum과 구하고자 하는 값인 n의 값이 같으면 결과값 변수 cnt를 증가 시키고, 끝 포인터를 오른쪽(증가시키기)으로 옮긴다. 그리고 옮긴 끝 포인터의 값을 sum에 추가한다.
• sum이 n보다 작을 때는, end포인터를 오른쪽으로 옮기고, sum에 end포인트 값을 추가한다.
• sum이 n보다 클 때는, sum에 start포인터 값을 빼고 start포인터를 오른쪽으로 옮긴다.
• 위 과정을 end포인트가 n과 같아지기 전까지 반복한다.

소스 코드

import java.util.*;

public class 수들의합5 {
	public static void main(String[] arg) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n+1];
		int cnt = 1; //정답
		int start = 1; //시작 포인터
		int end = 1; //끝 포인터
		int sum = 1; //시작 포인터와 끝 포인터의 구간 합
		for (int i = 1; i < n+1; i++) {
			arr[i] = i;
		}
		
		while (end < n) {
			if (sum == n) {
				cnt++;
				end++;
				sum = sum + arr[end];
			}
			else if (sum < n) {
				end++;
				sum = sum + arr[end];
			}
			else if (sum > n) {
				sum = sum - arr[start];
				start++;
			}
		}
		System.out.println(cnt);
	}
}

태클 감사합니다.
조언 환영입니다.