[JAVA] 백준 1806 부분합

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

1806번: 부분합

 

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

 

문제 풀이 

 

[백준/BOJ] 1806번 부분합 (C/C++) (tistory.com)

[백준/BOJ] 1806번 부분합 (C/C++)

 

- start, end 2개의 포인터로 부분합의 시작과 끝을 아래 조건에 따라 하나씩 늘려가면서 길이를 찾으면 됨 

 

1) 현재 부분합이 S보다 작은 경우 

 - end를 오른쪽으로 한 칸 이동하고 sum에 arr[end] 값을 더해준다. 

 

2) 현재 부분합이 S보다 크거나 같은 경우 

 - 현재 len값과 현재 부분합의 길이(end-start+1)를 비교하여 작은 값을 len에 기록 

 - 다음 탐색을 위해 sum에 arr[start]값을 빼주고 start를 오른쪽으로 한칸 이동 

 

 

정답 

 

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

public class Main 
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //수열의 길이
        int S = Integer.parseInt(st.nextToken()); //합
        
        int arr[] = new int[N+1];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
        {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int start = 0;
        int end = 0;
        int sum = arr[0];
        int len = N+1;
        
        while(start<=end&& end<N)
        {
            if(sum <S)
            {
                sum += arr[++end];
            }
            else
            {
                len = Math.min(len, end-start + 1);
                sum -= arr[start++];
            }
        }
        
        if(len == N+1) 
            len = 0;
        
        bw.write(String.valueOf(len));
        
        bw.flush();
        bw.close();
    }
}