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

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

이 문제는 배열을 응용하는 투 포인터를 사용하는 문제이다. 포인터를 2개를 사용하여 시간 복잡도를 줄이는 알고리즘이다.

Two Pointers

• list에서 연속된 범위를 구해야 할 때 두 개의 pointer의 위치를 기록하며 처리하는 알고리즘이다.
• 대표적으로 특정한 합을 가지는 부분 연속 수열 찾기가 있다.
• 시작 인덱스 : 연속된 수의 시작
• 끝 인덱스 : 연속된 수의 끝

로직

1. 시작 인덱스와 끝 인덱스를 배열의 맨 처음으로 초기화
2. 현재 합계를 끝 인덱스로 초기화 -> 두 포인터의 값을 계산
3. 끝 인덱스가 N보다 작거나 같을 때 까지 반복
   3-1. 현재 합계가 N과 같은 경우 : 횟수를 1 증가, 끝 인덱스를 1 증가, 합계를 계산 -> 다음 연속된 수를 고려하기 위함
   3-2. 현재 합계가 N보다 작은 경우 : 끝 인덱스를 1 증가, 맨 마지막 요소를 현재까지의 합계에 추가
   3-3. 현재 합계가 N보다 큰 경우 : 시작 인덱스를 1 증가, 인덱스 증가 전의 요소를 현재까지의 합계에서 빼기

초반에는 배열에 미리 수를 저장해 두고 풀려고 하였다. 하지만, 문제에서의 조건이 '연속된 자연수'이기 때문에 index를 1만 증가시켜주면 되지 배열에 굳이 저장하여 메모리를 낭비할 필요가 없다.

package silver5;

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

public class num2018 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //자연수
        int start = 0; //시작 index
        int end = 0; //끝 index
        int total = 0; //합계
        int result = 0; //합이 같은 경우의 횟수

        while(end <= N){
            if(total == N){ //합계가 같으면
                result ++; //횟수 1 증가
                end ++; //끝부분을 1 증가시켜 다음 요소들 판별할 수 있도록 함
                total = total + end;
            }else if(total < N){
                end ++;
                total = total + end;
            }else if(total > N){
                total = total - start;
                start++;
            }
        }
        System.out.println(result);
    }
}

여기에서 처음에는 if(total == N) 부분에서 total = total + end를 해 주는 것이 이해가 가지 않았다. total이 N과 같다면 횟수를 추가하고 total값에 더해주면 안된다고 생각했기 때문이다. 1+2+3+4+5의 경우를 예시로 들었을 때, total이 15고 end값이 6이기 때문에 total + end 값은 15 + 6이 되므로 조건에 부합하지 않다고 생각하였기 때문이다. 하지만, total값을 update 시켜줘야 while문이 돌아갔을 때, 맨 아래의 else if(total > N)으로 돌아간다는 사실을 깨달았다.