뚝딱뚝딱

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

💡 부분합

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

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

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

입력예시
10 15
5 1 3 5 10 7 4 9 2 8

출력예시
2

✅ 문제 풀이

부분합이라고 해서 무조건 크기가 N인 배열에 누적합을 구해 놓으면 해결될 문제가 아니다.

이 문제에서 핵심은 "한번만" 순회하여 해결해야 한다는 것이다.

처음에는 for문 안에 부분 while문을 넣어서 결론적으로는 o(n^2)의 시간복잡도로 구현하였다. 결과는 역시 시간초과였다.

부분합 문제는 특히 o(n)으로 해결해야 한다.

그럼 어떻게 해결할 수 있을까?

문제를 풀면서 인지하고 있었던 것은, 앞에서부터 누적해 나가되, 그 값이 S이상이 되면 멈추는 것이다. 그리고 다시 앞에서부터 하나씩 줄여갔을 때에도 여전히 S이상이라면 이전 보다는 더 짧은 길이가 될 수 있다는 점이다.

그러면 여기서 알 수 있는 점은, 시작 점과 끝점을 가리키는 두개의 포인터가 필요하다는 것이다.

우리는 그것을 st, en이라고 할 것이다. 그리고 그 값은 각각 1부터 시작한다.

그리고 부분합을 가리키는 total을 선언하고, st와 en이 현재 1을 가리키므로, total은 수열의 1번째 값을 갖도록 한다.

answer는 최소 길이인데, 현재 수열의 최대 값은 100000이기 때문에, 초기값을 100001로 설정하여 min값을 찾아가도록 한다.

이제 while문을 통해 수열을 순회하는데, 시작점인 st는 끝점인 en보다는 작거나 같아야 하며, en이 N과 같아질 때까지 순회하도록 한다.

그리고 아래의 조건에 따라 수행한다.

만약 현재 total이 S보다 크다면, 조건을 만족한 것이므로, 현재의 answer값 (st-en+1)=현재 total을 이루는 길이를 비교해서 더 작은 값으로 answer를 갱신한다.

만약 total이 S보다 작다면, en을 하나 늘려서 다음 값을 total에 누적해주고, total이 S보다 크다면, total에서 st가 가리키는 값을 빼준 후 st를 하나 줄여준다.

=> 이렇게 되면, st를 줄였을 경우에도 total이 S조건보다 커서 answer가 더 작은 값으로 갱신될 수 있기 때문에, 이런식으로 한번의 순회로 답을 찾아갈 수 있는 것이다.

순회가 끝나고 난뒤에는, answer가 초기값 100001이 아니라면 한번이라도 S보다 큰 부분합이 있었다는 것이므로 answer를 출력하고, answer가 초기값 그대로였다면, S보다 큰 부분합이 없었다는 것이므로 0을 출력하도록 한다.

전체코드는 아래와 같다.

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, S;
	cin >> N >> S;

	vector<int> vec(100001, 0);

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

	int answer = 100001;
	int total = vec[1];//첫번째 값부터 담아서 시작
	int st = 1;//시작 포인터
	int en = 1;//끝 포인터

	while (st <= en && en <= N) {
		if (total >= S) answer = min(answer, en - st + 1);
		if (total < S) {
			en++;
			total += vec[en];
		}
		else {
			total -= vec[st];
			st++;
		}
	}

	if(answer!=100001) cout << answer;
	else cout << 0;

	return 0;
}