[백준] B1806 부분합

문제

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

풀이

처음에는 분할정복법으로 접근 하려다가 복잡해질 것 같아서 관두고 문제를 다시 그려봤다.
연속된 부분 구간을 구해야 하므로 순서는 뒤바뀌면 안 된다.
누적합을 구하면서 주어진 값 S가 넘을 경우 가장 오래전에 넣은 값을 제거해나간다.
FIFO 형식을 가지고 있어 간단하게 큐를 사용해주었다.

• 0~n-1번째 값을 큐에 넣어가며 조건을 판단한다.
• minSize의 초기값은 n+1로 해준다.
  n이 아닌 이유는, 모든 요소를 포함할 때 조건을 만족하는 경우를 포함하기 위해서 !

1. A[i]를 큐에 넣어준다.
2. sum에 A[i] 값을 더해준다.
3. sum>=s일 경우,
   • sum이 s보다 작아지지 않는 선에서 queue의 front를 제거한 후 제거된 값을 sum에서도 빼준다.
   • minSize에 minSize와 queue.size 중 더 작은 값을 할당해준다.
4. A[n-1]까지 모든 요소를 체크했을 때,
   • minSize가 n-1 경우 0 출력
   • 아닌 경우 minSize 출력

모든 요소가 최소 1번 큐에 들어가고, 큐에 있는 값을 제거해가면서 조건을 만족하는 최소 길이를 구할 수 있다.

코드

int main(void) {
	int n, s;
	cin >> n >> s;

	int* arr = new int[n];
	
	for (int i = 0;i < n;i++) {
		cin >> arr[i];
	}
	
	vector<int> S;
	int sum = 0;
	int minSize = n+1;

	for(int i=0;i<n;i++) {
		S.push_back(arr[i]);
		sum += arr[i];
		
		if (sum >= s) {
			while (sum >= s) {
				if (sum - S[0] >= s) {
					sum -= S[0];
					S.erase(S.begin());
				}
				else {
					break;
				}
			}
			minSize = min(minSize, (int)S.size());
		}
	}

	if (minSize == n+1) cout << 0 << endl;
	else cout << minSize << endl;

}