[백준/Java] 2018번 수들의 합5 (투포인터)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 투 포인터
public class Main {
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 정수 N 입력받기
		int N = Integer.parseInt(st.nextToken());
		
		int count = 1; // N 본인일 경우 포함
		int start_index = 1;
		int end_index = 1;
		int sum = 1; // 연속된 숫자의 합
		
		while (end_index != N) // 오른쪽 포인터가 N이 아닐 때까지
		{
			if (sum == N) // 연속합이 N과 같으면
			{
				count++;
				end_index++;
				sum = sum + end_index;
			}
			
			else if (sum > N) // 연속합이 N보다 크면
			{
				sum = sum - start_index;
				start_index++;
			}
			
			else if (sum < N) // 연속합이 N보다 작으면
			{
				end_index++;
				sum = sum + end_index;
			}

		}
		
		System.out.print(count);
	}
}

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

2018번: 수들의 합 5

 

문제에 주어진 시간 제한은 2초입니다.

그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있습니다.

이런 상황에서는 O(nlogn) 시간 복잡도 알고리즘을 사용하면

제한 시간을 초과하므로

O(n) 시간 복잡도 알고리즘을 사용해야 합니다.

 

이런 경우 자주 사용하는 방법이

투포인터 입니다.

 

 

 

 

 

 

N 변수 저장

사용자 변수 초기화 (count = 1, start_index = 1, end_index = 1, sum = 1)

while ( end_index != N) {

     if (sum == N)        end_index 증가, sum 값 변경, count 증가

     else if (sum > N )  start_index 증가, sum 값 변경

     else if (sum < N)  end_index 증가, sum 값 변경

}

count 출력하기