[ 백준 / 1806 ] 부분합 (C++)

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

 

난이도 : 골드 4 
알고리즘 유형 : 투 포인터 
풀이 시간 : 24분 

문제 풀이 

길이 $N$인 수열에서 연속된 수들의 부분합 중에 그 합이 $S$ 이상이 되는 것 중 가장 짧은 길이를 구하자.

 

연속된 수들의 부분합을 구하는 문제이기 때문에, 정렬을 사용할 수 없다. 또한, 특정 구간이기 때문에 누적합을 사용할 수 없다. 따라서 본 문제는 투 포인터를 활용해 문제를 풀어나갈 수 있다.

 

먼저, 배열의 위치를 제공해줄 포인터 두 개 `left`, `right`를 생성하고, 수열의 0번 주소의 값으로 초기화를 진행해준다.

이후, 반복문을 통해 배열을 순회할 것인데, while 문을 사용하여 `left` 인덱스 번호가 `right` 인덱스 번호보다 커지는 경우가 아니라면 반복해서 순회를 진행해주었다. 

 

또한, 부분합 변수를 지정하여, 만약 부분합이 $S$보다 크거나 같다면, 현재 길이와 최소 길이를 비교하여 최솟값을 저장해주었고, `left` 인덱스를 1 증가시켜주었다. 반대로, 부분합이 $S$보다 작다면, `right`인덱스를 증가시키고, 값을 더해주었다.

각 포인터 `left`와 `right` 가 배열을 한 번씩 이동하기 때문에, 시간복잡도로는 $O(n)$이 소요된다.

 

코드

/*
길이 n짜리 수열이 주어진다. 
연속된 수들의 부분합 중, 그 합이 s 이상이 되는 것 중 가장 짧은 것의 길이 구하기

N <= 100000
풀이 : 
수열 정렬은 불가능하다.
1. 투포인터로 처음 위치부터 시작하기 
-> s가 넘어가면 left 줄이기 안넘어가면 right 올리기
*/

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, s;

int main() {
	cin >> n >> s;
	vector<int> arr(n + 1);
	for (int i = 0; i < n; i++)
		cin >> arr[i + 1];
	int left = 0, right = 0;
	int ans = 100000 + 2;
	int total = 0;
	while (left <= right) {
		if (total < s) {
			if (right < n + 1)
				total += arr[right++];
			else
				break;
		}
		else {
			ans = min(ans, right - left);
			total -= arr[left++];
		}
	}

	if (ans == 100002)
		ans = 0;
	cout << ans << '\n';


	return 0;
}

배운 점 

주어진 수열에 대해 순회하는 문제는 투 포인터를 활용하여 쉽게 풀 수 있었다.

자만하지 않고 더 노력해서 풀어나갈 것이다.