[백준]1806: 부분합 - JAVA

[백준]1806: 부분합 

www.acmicpc.net/problem/1806

1806번: 부분합

풀이

가장 짧은 길이의 부분합을 만족하는 길이를 출력하는 문제로 투포인터의 대표적인 문제라고 할 수 있다.

 

처음에는 투포인터 문제인줄 모르고 중첩 반복문을 사용하여 풀었다. 당연히 시간초과가 발생했고 투포인터 문제라는 힌트를 얻고 start, end 두 개의 인덱스 포인터를 사용하여 풀었다.

 

풀이 과정을 그림으로 표현하면 아래와 같다.

 

start와 end 포인터를 조건에 맞게 조작하며 최소 길이를 찾아 주었다. 투포인터를 이해하는데 가장 적합한 문제라고 생각된다. 나중에 다시 풀어봐야겠당.

 

코드

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int s = scan.nextInt();
        
        int[] nums = new int[n + 1];
        for(int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int total = 0;
        while(start <= n && end <= n) {
            if(total >= s && min > end - start) min = end - start;
            
            if(total < s) total += nums[end++];
            else total -= nums[start++];
        }
        
        if(min == Integer.MAX_VALUE) System.out.println("0");
        else System.out.println(min);
    }
}