백준 1806번 부분합 : 마포 코딩박

문제

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

사용한 알고리즘 : 투 포인터

포인터 두개 lo, hi 에 대해 ' lo이상 hi미만 '의 값들의 합을 sum 이라고 설정하였습니다.

투포인터를 진행하는 while 문을 돌립니다.
1. sum >= S 인 경우 ans를 최신화 하고 sum에서 lo의 값을 뺀 후 lo++

2. hi==N 인 경우 끝.

3. sum<S 인 경우 sum에 hi값을 추가 한 후 hi++

	#include <bits/stdc++.h>
	using namespace std;
	const int INF = 111111;

	int N, S;
	int arr[111111];
	int sum, lo, hi;
	int ans = INF;

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

	cin >> N >> S;

	for (int i = 0; i < N; ++i)
	cin >> arr[i];

	while(1){
	if(sum>=S){
	ans = min(ans, (hi-lo));
	sum-=arr[lo++];
	}
	else if(hi==N) break;
	else sum+=arr[hi++];
	}

	if(ans==INF) cout << 0 << '\n';
	else cout << ans << '\n';

	return 0;
	}

view raw BOJ 1806.cpp hosted with ❤ by GitHub