[백준][1806] 부분합

이 포스트는 백준 사이트의 부분합 문제 풀이입니다.

문제

해결 과정

이 문제를 처음 시도하였을 때, 주어진 배열을 정렬하고
정렬된 배열을 순차 탐색하면서 총 합이 S가 넘은 순간의 길이를 반환하려고 했습니다.

그러나 이러한 해결 방법의 문제점은 최단 길이가 아니라 최초 적합 길이가 반환된다는 점입니다.
예를들어, N과 S가 10, 20으로 주어지고 배열이 {5 5 5 5 1 4 4 4 4 4} 로 주어졌을 때,
정렬한 뒤 순차탐색으로 계산한다면 반환된 값은 5 입니다.

그러나 원하는 정답은 가장 짧은 부분합 길이이므로
반환되는 길이는 5개(4 + 4 + 4 + 4 + 4) 가 아니라 4개(5 + 5 + 5 + 5)가 되어야 합니다.
따라서 이 방법으로는 정확한 정답을 구할 수 없었습니다.

첫 번째 시도 (실패)

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

using namespace std;

int main() {
	int N, S;
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> S;

	vector<int> vec(N, 0);
	for (int i = 0; i < N; ++i) {
		cin >> vec[i];
	}

	sort(vec.begin(), vec.end());
	
	int sum = 0, len = 0;
	for (int i = N - 1; i >= 0; --i) {
		len += 1;

		sum += vec[i];
		if (sum >= S) {
			break;
		}
	}
	
	cout << (S > sum ? 0 : len);
	return 0;
}

두 번째 시도 (성공)

두 번째 시도에서는 정렬하지 않고 순차 탐색만을 이용해 값을 한 번에 구하고자 하였습니다.

가장 짧은 부분합을 구하기 위해서
부분의 시작점(low)와 끝점(high)을 설정하고 끝점을 한 칸씩(high += 1) 이동시키며 시작점부터의 합을 구하고
구한 합이 S를 넘긴 순간(sum >= S)의 길이(high - low + 1)를 사용해 최단 거리를 구하고자 하였습니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N, S;
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> S;
	vector<int> arr(N, 0);
	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
	}
	
	int sum = arr[0], len = N + 1;
	int low = 0, high = 0;

	while (low <= high && high < N) {
		if (sum < S) {
			high += 1;
			sum = sum + arr[high];
		}
		else {
			int newLen = high - low + 1;
			len = len > newLen ? newLen : len;
			
			sum -= arr[low];
			low += 1;
		}
	}

	cout << (len == N + 1 ? 0 : len);
	return 0;
}

실행 결과