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

<문제>

문제 출처 : https://www.acmicpc.net/problem/2018

<나의 풀이>

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);	// 받는 수가 작으니까 scanner 사용
        int N = sc.nextInt();
        int start_index = 1;	// 시작 지점의 인덱스
        int end_index = 1;	// 끝 지점의 인덱스
        int cnt = 1;	// N의 값을 먼저 저장함
        int sum = 1;	// 시작, 끝이 모두 1부터 시작해서
        while(end_index<N){
            if(sum<N){
                end_index++; sum = sum+end_index;
            }
            else if(sum>N){
                sum = sum - start_index;
                start_index ++;
            }
            else{
                cnt ++;
                end_index++;
                sum = sum+end_index;
            }
        }
        System.out.print(cnt);
    }
}

<핵심 개념>

투 포인터 문제는 주의해야 할 지점이 몇 가지가 있음.
1) 계산해야 할 데이터의 크기 유념하기
=> 이 문제에서 n이 10,000,000이므로 nlogn도 위험함. 그래서 O(n)의 시간복잡도 알고리즘으로 풀이해야 할 필요가 있음.
2) 구간 사이의 합을 구할 때 반드시 수가 정렬되어 있어야 함.