[백준] 1806_부분합 / 투포인터

 

 

Gold

 

 

문제

 

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다.

이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다.

둘째 줄에는 수열이 주어진다.

수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

 

출력

 

첫째 줄에 구하고자 하는 최소의 길이를 출력한다.

만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

 

 

 

---

 

풀이

 

import java.util.*;
import java.io.*; // BufferedReader, InputStreamReader

class Main {
    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());
        long S= Long.parseLong(st.nextToken());
        int[] arr = new int[N];
         st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        int s =0, e=0;
        long sum = 0;
        int min = Integer.MAX_VALUE;

        while(s<=e){
            if(sum >= S){
                min = Math.min(min, e-s);
                sum -= arr[s++];
            }else if(e==N){
                break;
            }else{
                sum += arr[e++];
            }
        }

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

 

 

해결방법

1. 투포인터를 활용하기 위해 시작점 s 와 끝점 e를 생성한 후 둘 다 0에 맞춘다. (처음부터 시작)

2. 배열의 합을 저장할 변수 sum을 생성한 후 0으로 셋팅한다. 

3. 부분합의 최소 길이를 저장하는 변수 min을 생성한 후 최댓값인 Integer.MAX_VALUE로 셋팅한다. 

4. 슬라이드를 이동시킨다. 

   - 현재 합 sum이 S보다 같거나 클 경우, 사용된 숫자의 갯수 (e-s)가 현재 min보다 작을 경우 업데이트한다. 이후 슬라이드의 스타트 시점을 이동시킨다.

   - 현재의 합이 S보다 작을 경우 끝지점을 이동시킨다.

   - 끝 지점 e가 배열의 끝에 도달하면 반복문을 종료한다. 

5. 구해진 부분합의 최솟값을 리턴하는데, min의 값이 여전히 최댓값이라면 만족하는 부분합이 없다는 의미이므로 0을 출력한다. 

 

 

 

 

---

 

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