[BAEKJOON] 1806번 부분합

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

1806번: 부분합

 

문제조건

 

1. 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이는?

접근방법

 

시간제한도 타이트하고, 입력값도 크게 주어지길래, 단순히 for문 두번 돌려서 O(n^2) 으로 시간이 걸리게 된다면 당연히 시간초과가 날 것이라고 생각했고, 문득 저번에 이런 비슷한 문제를 푼 경험이 떠올랐다.

2024.03.21 - [Algorithm/구현, 시뮬레이션] - [BAEKJOON] 20922번 겹치는 건 싫어

[BAEKJOON] 20922번 겹치는 건 싫어

바로 이 문제다!

투포인터로 대놓고 푸는 문제였다.

예외 사항은 S 이상이 될 수 없는 경우에는 0을 출력하는 것이었는데, 투 포인터에서 S보다 값이 커진적이 한번도 없어서 start값이 갱신되지 않은 경우이다.

 

소스코드

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

using namespace std;

int n, s, arr[100001];
int main(){
	cin >> n >> s;
	int res = 100001;
	for(int i = 1; i <= n; i++){
		int a;
		cin >> a;
		arr[i] = a + arr[i-1];
	}
	int start = 1, end = 1;
	while(end <= n){
		if(arr[end] - arr[start -1] < s) end++;
		else {		
			res = min(res, end - start + 1);
			start++;
		}
	}
	if(res == 100001) cout << 0;
	else cout << res;
	
}