[BOJ] 백준 1806. 부분 합

문제

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

1806번: 부분합

---

풀이

이전에 포스팅한 백준 2003. 수들의 합2 문제와 매우 유사합니다. 풀이 보러 가기

만약 수들의 합2 문제를 풀지 않으셨다면 위 문제부터 푸는 것을 추천드립니다.

 

위 문제의 풀이에서 포인터 사이의 간격을 최소로 갱신해주기만 하면 됩니다.

---

소스 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int S = sc.nextInt();
        int[] nums = new int[N+1];
        for(int i = 0;i<N;i++){
            nums[i] = sc.nextInt();
        }
        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = 0;
        while(left<=N&&right<=N){
            if(sum>=S&&min>right-left) min = right-left;
            if(sum<S) sum += nums[right++];
            else sum -= nums[left++];
        }
        if(min == Integer.MAX_VALUE) System.out.println(0);
        else System.out.println(min);
    }
}