[BOJ/CPP] 부분합 - 1806번 / C++ 풀이

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

1806번: 부분합

 

 

누적합 문제이다.

 

풀이 : 입력 받은 숫자를 하나씩 더하고 S보다 큰 부분이 나오면 제일 왼쪽의 배열을 뺴주면서 최소 길이를 갱신해야한다.

 

예제로 설명을...

N = 6, S = 5

입력 받을 배열 { 1, 3, 1, 2, 3, 1 }

 

 

1을 입력받고 Sum에 1을 더해준다.

아직 S를 넘지 못하였다.

 

다음 숫자을 입력받아 Sum에 더해주자

 

S = 5, Sum = 4로 아직 S보다 작다. 하나 더 받아서 더해보자

 

 

드디어 sum의 값이 S 이상이 되었다!

이제 답을 갱신해주면

ans = i(현재 위치) - start(배열의 시작위치) + 1, 즉 1 + 2 - 0 = 3으로 답이 갱신된다.

 

3보다 더 짧은 길이가 있을 수도 있으니 계속 해보자!

 

 

2를 입력받아 Sum에 더했더니 sum은 7이 되고 길이는 4로 더 늘어나버렸다....

 

이제 최소 길이를 구하는 알고리즘을 적용해야 한다.

현재 누적 합(sum)에서 start 포인터가 위치하고 있는 값을 빼보았을때 그 값이 여전히 S를 넘는다면 Start에 위치한 배열은 쓸모가 없게 된다.

if(sum - arr[start] >= S){
	sum = sum - arr[start];
	start++;
}
ans = min(ans, i - start + 1);

다시 답을 갱신해보면 ans = i - start + 1 = 3

길이가 늘어나지 않았다!

sum은 6이 되고 ans는 3이 되어 다시 최소 길이로 만들었으니 다음 배열로 가보자.

 

start 포인터를 한 칸 땡겨줬고, 새로운 숫자로 3이 들어와서 SUM은 9가 되었다.

 

맨 좌측 배열이 필요없는 배열인지 확인하기 위해 위에서 했던 작업인 sum - arr[start]를 진행하면 sum은 6이 되고 여전히 S보다 큰 숫자를 유지하고 있다.

start가 가리키는 배열을 한 칸 땡겨주고 ans를 갱신해준다. (ans = 4 -> 3)

 

 

이번에도 sum - arr[start] >= S인지 확인한다.

6 - 1 >= 5 이므로 1도 필요없는 숫자가 되었다!

1도 버려주고 Start 포인터를 한 칸 땡겨준다.

 

ans의 최소 길이는 2가 되었다!

 

마지막으로 1을 받아주면

 

 

ans = i - start + 1이므로 마지막 숫자까지 받았을때의 길이는 3이 되지만, 현재까지 나온 ans의 최솟값과 비교해 최솟값만 저장하기 때문에 ans는 2로 마무리된다.

 

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int n, s; cin >> n >> s;

	int ans = 1e9;
	int sum = 0;
	int start = 0;
	vector <int> vc(n);

	for (int i = 0; i < n; i++) {
		int c; cin >> c; vc[i] = c;
		sum += c;
		if (sum >= s) {
			while (sum - vc[start] >= s) {
				sum -= vc[start];
				start++;
			}
			ans = min(ans, i - start + 1);
		}

	}
	if (ans == 1e9)
		cout << '0';
	else
		cout << ans;
}