[백준 - 1806] 부분합 .java

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

 

• 두 포인터 같은 방향으로 이동=> i 고정해놓고 r 이동 
• 현재 합이 s보다 작고 r이 n-1보다 작은 범위에 속할때 => r을 하나 이동
• 우측 포인터가 증가하여 curSum이 s 이상이 되면, 그 구간의 길이를 계산하여 count에 저장
• 그 구간의 최소 구간 길이 갱신

if (answer > n) answer = 0; 

부분합이 s 이상인 연속된 구간이 없을 경우, 결과로 0을 출력

 

이 문제는 정렬을 하면 안되기에 for문으로 왼쪽포인트를 하나씩 증가해가면서 오른쪽 포인터을 통해 해당 조건에 부합하는 값들을 구하면 된다

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;


public class test1 {

    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        long s = sc.nextLong();

        int[] nums = new int[n];

        for(int i=0;i<n;i++)
            nums[i]=sc.nextInt();

        int r=0, answer =n+1;
        long curSum = nums[0];//현재 부분합
        int count=1;//부분배열의 길이 -> 0번 숫자 추가함
        for(int i=0;i<n;i++){
        //우측 포인터 r을 오른쪽으로 이동시켜가며 합이 s 이상이 되도록 확장
            while(curSum<s && r<n-1) {
                count++;
                curSum+=nums[++r];//r을 증가시키고 해당 값 추가
            }
            if(curSum>=s){
                count=r-i+1;//현재 구간의 길이
                if(count<answer){
                    answer=count;
                }

            }
            //현재 i가 포함되는건 다해봄 -> 합에서 빼기
            curSum -=nums[i];
        }
        //n보다 큰 답은 없음 -> 0 출력
        if(answer>n) answer = 0;
        System.out.println(answer);
    }

}