부분합(백준_1806)

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

1806번: 부분합

 

문제설명

5 1 3 5 10 7 4 9 2 8 중 부분합으로 15 이상인 수열 중 가장 길이가 짧은 것을 찾는 것이다.

{5, 10} {10, 7}이 제일 짧다.

 

문제에 대한 아이디어

부분합과 수열의 길이를 구하라는 것에서 투 포인터를 써야겠다고 생각했다.

 

제일 처음 시작 할 때, First = 0, Second = 0; sum =0; count =0;이다.

1. sum < s 이면 지금 자신을 더하고 second를 뒤로 보낸다.

2.  sum >= s 이면  count를 샌 뒤 답과 최솟값을 비교한다.

     sum에서 지금 자신을 뺀 뒤 first를 하나 앞으로 이동시킨다. 

구현

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 buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(buf.readLine());
        int pro[] = new int[n+1];
        for(int i =0; i<n;  ++i){
            pro[i] = Integer.parseInt(st.nextToken());
        }
        int first = 0;
        int second = 0;
        int sum = 0;
        int result= Integer.MAX_VALUE;
        int count = 1;
        boolean check = false;
        while(second <= n) {
            if(sum >= s)  {
                sum -= pro[first++];
                count = second - first + 1;
                result = Math.min(result, count);
                check = true;
            }
            else if(sum < s){
                sum += pro[second++];
            }
        }
        if(check)  System.out.println(result);
        else System.out.println(0);
    }
}

배열의 size가 n+1인 이유

10 10
1 1 1 1 1 1 1 1 1 10 (index는 9까지 존재)
이런 상황일 경우를 생각해 보면 된다.
 second는 10까지 가고 first는 0인 상태에서 합은 19이다. 하지만 이 이후부터 start가 하나씩 앞으로 오는 부분을 수행해야 한다. 
즉, 정답이 제일 마지막 인덱스 하나를 가질 때 도 있으므로 배열의 크기를 수열보다 하나 더 크게 만들었다,

 

https://github.com/Heron-Woong/CodingTest_Practice/commit/ab67be19125f8ae4263a9d766073e5c316c86f64

백준_1806, 부분합 · Heron-Woong/CodingTest_Practice@ab67be1