[백준] Gold IV. 부분 합

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

 

사용 알고리즘

• 투 포인터

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n, s;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());

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

        if (total < s) {
            System.out.println(0);
            return;
        }

        int hi = 0;
        int min = Integer.MAX_VALUE;
        long sum = 0;

        for(int lo = 0; lo < n; lo++) {
            while(hi < n && sum < s) { // 끝점에 도달하거나, 부분합이 s이상이면 탈출

                if (hi != n) {
                    sum += arr[hi];
                    hi++;
                }

            }

            // 탈출했을 때 길이의 최솟값을 갱신해줘야 함.
            if (sum >= s) {
                min = Math.min(min, hi - lo);
//                System.out.println("len: " + (hi - lo) + " sum: " + sum);
                sum -= arr[lo]; // 부분합에서 시작점을 빼줘야 다음 탐색이 가능.
            }
        }

        System.out.println(min);

    }
}

 

 

회고

 

이번 문제도 5일전에 풀었을 때는 손도 못댔는데, 오늘 다시 푸니까 어렵지 않게 풀렸다. 다만, 문제에서 마지막 조건이 sum이 s를 만드는 것이 불가능한 경우 0을 출력하는건데 깜빡해서 자꾸 틀렸다.

 

입력값을 받으면서 합을 계산해주고 (몰랐는데 입력값을 받을 때 시간복잡도가 없다고한다 ?!) 그 합이 s보다 작다면 0을 출력 후 즉시 return을 해주면 된다. 

 

문제에서 가장 까다로운 부분은, while문을 빠져나왔을 때 sum에서 arr[lo]를 빼줘야 순차적으로 탐색이 가능하다.

10 15
5 1 3 5 10 7 4 9 2 8

 

이렇게 예제가 주어졌을 때, 처음 합이 15를 넘는 지점을 생각해보면

(5,1,3,5,10)이다. 

 

합이 15보다 크므로 시작점을 업데이트 해주는데, while문의 (sum < s) 조건을 계속 실행시켜주기 위해서는 시작값을 뺴서 업데이트를 시켜줘야 한다.

 

(1,3,5,10) -> 이때도 15보다 크므로

(3,5,10) 

(5,10)

 

(10, 7)

 

이렇게 된다. 이런식으로 시작점을 오른쪽으로 옮겨주는 것 뿐만 아니라 sum도 시작값을 빼줘서 오른쪽으로 이동시켜 주게된다!