[백준 1806] 부분합 with JAVA

www.acmicpc.net/problem/1806 

1806번: 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

import java.io.*;
import java.util.*;

public class p1806 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[n+1];
        int s = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0;
        int end = 0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;

        while(end <= n && start <= n){
            if (sum >= s){
                ans = Math.min(end - start, ans);
                sum -= arr[start];
                start++;
            } else {
                sum += arr[end];
                end++;
            }
        }
        if (ans == Integer.MAX_VALUE) System.out.println(0);
        else System.out.println(ans);
    }
}

 

어려웠던 점:

1. 투 포인터를 생각하지 못하고, 완전탐색으로 풀었었다.

2. 투 포인터 개념을 잘 이해하지 못해, 각 포인터가 정하는 범위에 대해 잘 이해하지 못했다.

3. 투 포인터가 이동할 때, start가 이동하면 end를 0으로 옮기지 않아도 되는 이유에 대해 이해하지 못했다.

4. 투 포인터로 탐색을 할 때, 그것이 길이의 최소값을 보장해준다는 것을 이해하지 못했다.

 

풀이법:

두 개의 포인터를 설정해준다. start = 0, end = 0;

이 때, start에서 end의 값이 내가 계산하고자 하는 부분합이다. (ex. start = 0, end = 4일 경우, 배열의 0부터 4까지의 부분합)

부분합이 원하는 s보다 같거나 클 때는

  기존의 답이라고 생각했던 크기(ans)와 현재 부분합의 크기(end - start)를 비교해 더 작은 값을 비교해 ans에 저장해준다.

  그 후, sum에 arr[start]를 빼고 start를 1 증가시킨다.

부분합이 원하는 s보다 작을 때는

 sum에 arr[end]를 더하고 end를 1 증가시킨다.

 

while 루프 종료 조건:

end가 행렬의 마지막까지 갔음에도 sum을 넘기지 못했을 때 (start를 늘려도 부분합은 더 작아질 뿐이다.)

start가 행렬의 마지막까지 갔을 때 (완전 탐색 완료)