백준 1806 (부분합)

문제

---

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

 

 

 

풀이

---

연속된 수들의 부분합이기 때문에 두개의 포인터를 이용해서 구했다.

 

5

1

3

5

10

7

4

9

2

8

이렇게 배열이 있다면, left = 0 right = 0 부터 시작해서 S보다 크거나 같으면 left 값을 빼주고 s 보다 작다면 right값을 더해주는 방식으로 풀었다.

while(true) {
			
	if(sum >= s) {
		sum -= arr[left++];
	}
	else if(right >= arr.length) {
		break;
	}
	else if(sum < s) {
		sum += arr[right++];
	}
	
	if(sum >= s){
		min = Math.min(min, right - left);
	}
}

위 코드를 보면 이해하기 쉬울 것이다.

S 이상이 됐을 때, 최소갯수를 구하는 것이 문제이므로 그때 최솟값을 저장해준다.

 

시간복잡도를 줄이는 것이 어려워 보이지만 두 포인터를 이용한 완전탐색을 알고있었다면 반복문을 여러개 사용하지 않고 풀 수있다.

 

 

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static int n, s;
	static long[] arr;

	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(bufferedReader.readLine());
		arr = new long[n];
		for(int i = 0 ; i < n ; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		
		int left = 0, right = 0;
		long sum = 0;
		int min = Integer.MAX_VALUE;
		while(true) {
			
			if(sum >= s) {
				sum -= arr[left++];
			}
			else if(right >= arr.length) {
				break;
			}
			else if(sum < s) {
				sum += arr[right++];
			}
			
			if(sum >= s){
				min = Math.min(min, right - left);
			}
		}
		
		if(min == Integer.MAX_VALUE) {
			min = 0;
		}
		
		System.out.println(min);
	}	
}