백준 2018 Java

투 포인터

 

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

 

문제 분석

문제에 주어진 시간 제한은 2초입니다 그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀 있습니다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과 하므로 O(n)의 시간 복잡도 알고리즘을 사용해야합니다. 이런 경우 자주 사용하는 방법이 투 포인터입니다.

연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료인덱스를 지정하여 연속된 수를 표현하겠습니다.

 

 

- start_index와 end_index 사이의 합(sum)이 N보다 작을 경우에는 end_index를 증가시켜주고 둘의 합이 N보다 크다면 sum - start_index를 해주고 start_index를 증가시켜 줄것입니다.

투 포인터 이동 원칙

• sum > N: sum = sum - start_index; start_index++;
• sum < N: end_index++; sum = sum + end_index;
• sum == N: end_index++; sum = sum + end_index; count++;

 

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