[백준 1806번] 부분합

[백준 1806번] 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

 

 

 문제

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

 

 입력

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

 

 출력

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

 

 

 풀이

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, S;
	int arr[100000]={0,};
	int sum[100000]={0,};
	cin >> N >> S;
	for(int i=0;i<N;i++){
		cin >> arr[i];
		if(i==0) sum[i] = arr[i];
		else sum[i] = sum[i-1] + arr[i];
	}
	
	int lp = 0;
	int rp = 0;
	int s = 2147483647;
	while(rp!=N){
		int k = sum[rp] - sum[lp] + arr[lp];
		if(k >= S){
			if(rp - lp + 1 < s) s = rp - lp + 1;
			if(k == S) rp++;
			else lp++;
		}
		else rp++;
	}
	
	if(s == 2147483647) cout << 0;
	else cout << s;
	return 0;
	
}

 맞왜틀에 빠져서 반례찾느라 5트만에 성공했다. 불가능할 때 0처리를 안해서 틀린 건 금방 찾았는데, while문에서 k>=S일때 lp++인 줄 알았는데 11 10 1 1 1 1 1 1 1 1 1 1 10 의 입력에서 에러가 발생했다. 이유는 k==S일때는 lp++가 아닌 rp++를 해야하기 때문이다. 찾는데 좀 걸리긴 했지만 수정하니 바로 정답을 받았다. 이 문제를 풀면서 누적합도 사용해봤는데 굳이 사용안하고 sum 변수로 일일히 처리해도 될듯 싶다.