문제

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

---

풀이

누적합, 투포인터

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

// 연속된 부분합 >= S
// 그 중에서 최소 길이 출력 

const int MAX = 100001; 
int psum[MAX]; // 누적합 배열 

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

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

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

		if(i == 0) psum[i] = v[i];
		else psum[i] = psum[i - 1] + v[i];
	}

	int l = 0, r = 0;
	int ans = 1e9;
	int sum = 0;
	
	while(l <= r && r < N){
    	// 엣지 케이스 처리 
		if(l == r) sum = v[l];
		else if(l == 0) sum = psum[r];
		else sum = psum[r] - psum[l - 1];
		
		if(sum >= S){
        	// 부분 수열의 길이의 최솟값 
			ans = min(ans, r - l + 1); 
			l++;
		}else{
			r++;
		}
	}

	if(ans == 1e9) cout << "0\n";
	else cout << ans;

	return 0;
}

누적합과 투포인터를 이용하여 시간복잡도 O(N)에 해결할 수 있다. N이 최대 10만이므로, O(N^2)으로 풀면 반드시 시간초과가 발생한다.

슬라이딩 윈도우, 투포인터

굳이 누적합 배열을 만들지 않고도 다음과 같이 슬라이딩 윈도우 방법으로도 풀 수 있다. 메모리 공간을 더 절약할 수 있다.

• v[l] ~ v[r - 1] 까지 부분 수열의 합이 S 이상인지 검사
• S 이상이면
  • 기존 길이와 (r - l)을 비교하여 최솟값 저장
  • 왼쪽 원소를 합산에서 제외
  • 인덱스 갱신 l++
• S 미만이면
  • 오른쪽 원소를 합산에 추가
  • 인덱스 갱신 r++

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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

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

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

	int l = 0, r = 0;
	int ans = 1e9, sum = 0; 

	// sum: v[l] ~ v[r - 1] 까지의 부분합 
	while(l <= r && r <= N){
		if(sum >= S){
			// 부분 수열의 길이의 최솟값 
			ans = min(ans, r - l);
			sum -= v[l++];
		}else{
			if(r == N) break;
			sum += v[r++];
		}
	}

	if(ans == 1e9) cout << "0\n";
	else cout << ans;

	return 0;
}

주의할 점은 이전 풀이에서는 v[l] ~ v[r] 까지의 합이지만, 현재 풀이에서는 r이 부분 수열의 마지막 원소 '바로 다음 위치'를 가리킨다는 것이다!

그래서 while문을 보면 r이 N까지 커진 경우에도 반복문 안으로 들어가서 최솟값 갱신을 시켜줘야 한다.

r < N 으로 조건문을 작성하면 틀린다!

• 누적합 배열 사용
  

• 슬라이딩 윈도우 (메모리 사용량 감소)