[백준 1806 - Java] 부분합

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

1806번: 부분합

 

문제

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

풀이

저는 이 문제를 큐를 이용해서 풀이하였습니다. 이 방식대로라면 합이 되는 수열의 원소들만 큐 안에 들어있게 됩니다!

 

우선 최솟값을 N+1로 초기화한 후 풀이를 시작합니다.

수열의 0번째 값부터 큐에 넣어주면서 S와의 비교를 하며 큐에서 빼거나 넣어주면 됩니다.

큐 안의 수의 합이 S보다 큰 경우 큐의 front 값을 빼도 그대로 S 이상일 땐 해당 값을 pop해줍니다.

그런 뒤 큐의 사이즈를 현재 최솟값과 비교해서 큐의 사이즈가 더 작은 경우 현재 최솟값을 업데이트 해줍니다.

 

먄약 모든 수열에 대해서 확인한 후에도 최솟값이 N+1이라면 이 때는 S를 절대 넘지 못하는 것이므로 0이 답이됩니다.

 

import java.util.LinkedList;
import java.util.Queue;
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[] arr = new int[N];
		int answer = N+1;
		int idx = 0;
		int sum = 0;
		
		Queue<Integer> q = new LinkedList<Integer>();
		
		
		for(int i=0; i<N; i++)
			arr[i] = sc.nextInt();
		
		
		while(idx<N) {
			q.add(arr[idx]);
			sum+= arr[idx];
			while(sum > S && q.size() > 0) {
				int f = q.peek();
				if(sum-f >= S) {
					sum = sum-f;
					q.poll();
				}
				else
					break;
			}
			
			if(sum >= S) {
				if(q.size() < answer)
					answer = q.size();
			}
			
			idx++;
		}
		
		if(answer == N+1)
			answer = 0;
		
		System.out.println(answer);
	}

}