[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을 출력하면 된다.

 

 

풀이

 

수열에서 연속된 자연수들의 부분합을 구하는 문제이기 때문에 투포인터를 사용해서 문제를 풀 수 있다.

---

 

[ start와 end 두개의 포인터를 사용해서 수열안에 연속된 수의 부분합을 구할 수 있다 ]

 

• start <= end의 조건을 만족한다
• end가 수열의 길이 보다 커진다면 탐색을 종료한다.

 

[ 부분 합(sum)과 입력받은 합(S)과 비교해서 부분합을 바꾼다 ]

 

• sum <= S 이면 최소 길이를 구하는 조건에 부합하기 때문에 min을 사용해서 최소 길이(end - start + 1)를 구하고 다음 부분합을 구하기 위해 start 포인터를 오른쪽으로 이동한다. 이동하기 전 값을 빼서 부분합을 다시 구할 수 있다.                                                                                                                         sum -= arr[start++]
• sum >   S 이면 구한 부분합이 조건에 만족하기 위해서 수열의 길이를 늘려줘야하기 때문에 end 포인터를 오른쪽으로 이동한다. 그 후 이동한 값에 대해서 부분 합을 다시 구할 수 있다.                                           sum += arr[++end]

 

[ 출력 ]

 

min값을 구한 적이 없다는 것은 한번도 부분합이 S이상이 된적이 없다는 것과 같다. 즉 sum이 초기 값인 100001이 들어 있다면 ans에 0을 넣고 이를 출력한다.

 

코드

#include <iostream>
using namespace std;
int arr[100001];

int main() {

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, S, sum;
	int start = 0, end = 0;
	int ans = 100001;
	cin >> N >> S;

	for (int i = 0; i < N; i++) cin >> arr[i];
	sum = arr[0];

	while (1) {

		//무한루프 종료조건
		if (end == N) break;

		//부분 합이 변하는 조건
		if (sum >= S) {
			ans = min(ans, end - start + 1);
			sum -= arr[start++];
		}
		else {
			sum += arr[++end];
		}

	}

	if (ans == 100001) ans = 0;
	cout << ans;

	return 0;
}