[백준_1806]_부분합

LINK

문제설명

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

요구사항

합이 s가 되도록 무작위로 수를 뽑아 합이 S가 되는 것이 아닌 연속된 index를 가진 수열이다.
합이 s가 되는데 연속접으로 idx를 갖는 값이 있으면 가장 길이가 짧은 길이의 값을 반환하는 문제이다.

※투포인터 기본문제

코드 설명
왼쪽포인터 오른쪽포인터를 0으로 초기 설정 후 왼쪽,오른쪽 포인터를 계속 이동시키면서 합이 s가 되는 경우를 찾는다.
오른쪽 포인터를 합이 s가 되거나 이상이 되면 길이가 몇 인지를 측정한다.
그리고 그 동안은 오른쪽포인터를 이동하였으니 왼쪽포인터를 오른쪽으로 땡긴다. 그리고 계속 오른쪽 포인터를 옮기다가 값이 s이상이 되면 다시한번 이전의 길이와 현재길이를 비교한다.
만약 오른쪽 포인터의 이동이 n에 다다르게 되면 루프문을 종료한다.

package AL_CS_STUDY.Weekly14;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class subSequenceSum {
    static int n,arr[];
    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());
        int s=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 ans=Integer.MAX_VALUE;
        int sum=0;
        int ptr1=0;
        int ptr2=0;
        while (true)
        {
            if(sum>=s)
            {
                ans=Math.min(ans,(ptr2-ptr1));
                sum-=arr[ptr1++];
            }
            else if(ptr2==n)
                break;
            else
            {
                sum+=arr[ptr2++];
            }
        }
        if(ans==Integer.MAX_VALUE)
            System.out.println(0);
        else {
            System.out.println(ans);
        }
    }

}