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

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

1806번: 부분합

 

문제 분석

10000 이하의 자연수로 이루어진 수열에서 부분 연속합이 S이상 되는 것 중에서 가장 짧은 것의 길이를 구하는 문제다. 투 포인터를 사용하여 조건을 충족하는 것들 중 가장 짧은 것의 길이를 구하면 된다.

 

코드

#include <iostream>
using namespace std;

int main(){
	int n, m; cin>>n>>m;
	int a[n+1];
	
	for(int i=1; i<=n; i++)cin>>a[i];
	
	int start = 1, end = 1, count = 0, length = 0, min = n;
	int result = a[1];
	
	while(start<=end&&end<=n){
		if(result<m){
			result+=a[++end];
		}
		else if(result>=m){
			count++;
			length = end - start+1;
			if(length< min) min = length;
			result-=a[start];
			start++;
			if(start>end){
				end = start;
				result = a[start];
			}
		}
	}
	if(count==0)cout<<0;
	else cout<<min;
	
	return 0;
}

 

문제 풀이

1. 수의 개수 n, 조건이 되는 수 m, 수열 a를 입력받는다.
2. 첫 번째 포인터 start, 두 번째 포인터 end를 1로 설정하고, 조건을 충족하는 부분 연속합을 만들 수 없을 때를 판별하기 위한 count 변수와 부분 수열의 길이 length, 최소 길이를 구하기 위한 min 변수를 선언한다. 그리고 부분 연속합인 result의 초기값을 a[1]로 설정한다.
3. start가 end보다 크지 않고 end가 n이하일 동안 while문이 돌아가도록 하여 두 포인터가 역전되거나 두 번째 포인터가 수열 밖으로 나가지 않도록 한다. 부분 연속합이 m보다 작으면 조건을 충족하지 못하므로, 부분 연속합에 수열의 다음 인덱스의 수를 더해준다.
4. 3을 반복하다가 조건을 충족하게 되면(부분 연속합이 m이상이 되었을 때), 조건을 충족하는 경우가 늘었으므로  count를 1 증가시키고  길이를 구하여 이 길이가 현재 최소값인 min보다 작을 때 min을 현재 길이로 설정한다. 지금 길이가 현재의 start위치에서 제일 짧은 것이므로 부분 연속합에서 a의 start 인덱스 값을 빼주고 start를 1 증가시킨다. start가 1 증가하여 길이가 줄었는데도 조건을 충족하면 min이 재설정될 것이고 아니라면 위의 과정을 반복할 것이다.
5. 4에서 start 값이 1 증가했을 때 end보다 커지게 된다면, end를 start와 동일하게 설정하고, 부분 연속값을 a의 start 인덱스 값으로 설정하여 포인터가 역전되는 것을 막는다.
6. count 값이 0이라면 즉, 조건을 충족하는 경우가 없었다면 0을 출력하고 아니라면 최소 길이인 min을 출력한다.