[백준] 2018_수들의 합5 - JAVA

백준_2018

2018번: 수들의 합 5

 

투 포인터

투 포인터는 말 그대로 2개의 포인터이다. 이 두 개의 포인터를 이용해서 알고리즘의 시간 복잡도를 최적화할 수 있다.

예제에 나온대로 N의 값이 15라 할때 연속된 자연수의 합은 15(자기 자신), 7+8, 4+5+6, 1+2+3+4+5 이렇게 4개이다. 

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

 

투 포인터의 이동 원칙

sum > N : sum -= startIdx; startIdx++:
sum < N : sum += endIdx; endIdx++;
sum == N : endIdx++; sum += endIdx; count++;

 

간략하게 N이 10이라 가정해보자. 그림으로 배열을 예시들어 설명했지만 굳이 배열을 생성하지 않아도 풀 수 있는 문제이다.

뒷부분 생략

startIdx가 노랑, endIdx가 파랑이다. 반복문을 한 번 돈 상태이며 sum의 값은 6, count는 1이다. count는 자기 자신을 카운트해서 1이라는 숫자로 초기화 해 놓은 상태이다. 현재 상태에서 sum은 N보다 작으므로 투 포인터 이동 원칙에 따라 sum에 endIdx를 누적 저장하고 endIdx값을 증가한다.

이제 sum은 10, count는 1이다. sum과 N의 값이 같으므로 투 포인터 이동 원칙에 따라 endIdx를 증가시키고, sum에 endIdx를 누적 저장한 뒤 count를 증가시킨다. 

이런 식으로 endIdx가 N이 될때까지 반복하면 된다.

 

코드

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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int input = Integer.parseInt(st.nextToken());

        int count = 1;
        int sum = 1;
        int startIdx = 1;
        int endIdx = 1;

        while(endIdx != input) {
            if(sum == input) {
                count++;
                endIdx++;
                sum += endIdx;
            } else if(sum > input) {
                sum -= startIdx;
                startIdx++;
            } else {
                endIdx++;
                sum += endIdx;
            }
        }
        System.out.println(count);
    }
}

 

문제를 맨 처음에 봤었을 때는 '구간 합'이 제일 먼저 떠올랐지만 좀 더 생각해보니 1부터 N까지의 연속된 자연수를 구하는 거라 굳이 배열이 필요 없다고 생각해서 나름 잘 푼 문제..!

 

제출 결과