[BOJ G4][#투포인터]1806번 부분합

부분합 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (하단 참고)

128 MB

103034

28618

20227

26.004%

문제

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

2

 

📝풀이

일단 정보를 보자마자 투포인터를 떠올릴 것이다.

 

일단 처음에 모든 과정을 검색하는 브루트포스를 사용해보았다.

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

public class Main {
    static int arr[];
    static int N,M;
    static int pointer;
    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());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        
        int count = Integer.MAX_VALUE;
        for(int i = 0; i < N; i++){
            pointer = i;
            while(isIndexVaild(pointer)){
                if(solve(i, pointer)){
                    count = Math.min(count, pointer-i+1);
                    break;
                }else{
                    pointer++;
                }
            }
        }

        System.out.println(count);

    }
    public static boolean solve(int i, int pointer){
        int sum = 0;
        for(int j = i; j <= pointer; j++){
            sum += arr[j];
        }
        return sum > M;
    }
    public static boolean isIndexVaild(int pointer){
        return pointer >= 0 && pointer < N;
    }

}

결과는 시간초과 

 

처음부터 다시 떠올려보자 

 

이 문제 자체가 투포인터가 어떻게 사용하는 지가 중요하다. 해당 부분은 첫번째에서 포인터를 15이상까지 간 것이다.

 

다음 것도 확인해보자

오른쪽 포인터는 고정되고 왼쪽 포인터가 1이 증가한 것을 알 수 있다. 이유가 무엇일까??

그것은 왼쪽 포인트가 만족되었을 때 왼쪽 포인터 1개를 제외해도 여전히 15를 넘기 때문이다. 

 

즉 누적 합에 대해서 하나의 수가 끝났을 때 그 수를 뺀 다음도 15를 넘으면 해당 수는 검사가 끝났다는 것이다. 

다음 것도 15를 넘기 때문에 누적 합에서 왼쪽 포인터만 뺀 것을 알 수 있다. 

길이는 가장 작은 것을 구하면 되므로 이제부터 쉽게 구현할 수 있다.

 

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

public 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());
        int S = Integer.parseInt(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 minLength = Integer.MAX_VALUE;
        int left = 0; // 왼쪽 포인터
        int sum = 0; // 누적합
        
        for (int right = 0; right < N; right++) {
            sum += arr[right];
            
            while (sum >= S) { //만약 15를 넘는다면 왼쪽 포인터를 빼고 그것도 15를 넘는지 검사
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left++];
            }
        }
        
        if (minLength == Integer.MAX_VALUE) {
            System.out.println(0);
        } else {
            System.out.println(minLength);
        }
    }
}