[백준] 1806번 부분합(java)

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

1806번: 부분합

이 문제는 부분합과 투포인터를 사용하면 쉽게 풀 수 있다.

 

핵심

연속된 수를 계속해서 더하다가 합이 원하는 s의 값 이상이 되면 시작점을 한 칸 앞으로 당겨온다.

이후 나머지의 합을 비교하여 계속 s이상이면 다시 시작점을 당기고, 아니면 끝지점을 한 칸 올린다.

자세한 건 코드를 통해 확인해 보자.

 

 

정답 코드

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nAndS = br.readLine().split(" ");
        int n = Integer.parseInt(nAndS[0]);
        int s = Integer.parseInt(nAndS[1]);

        String[] arrInfo = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(arrInfo[i]);
        }

        int sum = 0;
        int length = Integer.MAX_VALUE;
        int start = -1;

        for (int end = 0; end < n; end++){
            sum+=arr[end];
            if (sum>=s){
                while (sum>=s){
                    length = Math.min(length,end-start);
                    start++;
                    sum-=arr[start];
                }
            }
        }

        if (length == Integer.MAX_VALUE) System.out.println(0);
        else System.out.println(length);
    }
}

해설

앞서 말한 대로 입력값을 모두 저장시킨다.

이후 탐색을 시작한다.

start를 -1로 설정하였다. 탐색을 0부터 하기 때문이다.

만약 처음부터 s를 넘길 경우 0 - - 1인 1이 된다.

현재의 합이 s이상일 경우 start를 1 증가시키고, 그 값을 뺀다.

이후 다시 값을 비교한다.

이것을 반복하면 최소 길이를 알 수 있다.

만약 length가 max_value인 경우에는 모든 합을 더해도 s이상인 경우가 없다는 것을 의미한다.

따라서 0을 출력한다.

 

 

배운 점

투 포인터를 사용하는 알고리즘을 종종 보는데, 사용할 때마다 재미있다는 생각이 든다.

투 포인터를 제대로 사용하면 시간복잡도를 크게 줄일 수 있기 때문에 이와 같은 알고리즘에 익숙해지자.