(C++) BOJ/백준 1806 - 부분합

문제 출처 : BOJ 1806 - 부분합 www.acmicpc.net/problem/1806

 

이번 문제도 투포인터를 이용하는 문제이다.

이번 문제는 부분합이 s 이상인 부분합들 중에서

길이가 가장 짧을 때의 길이를 출력하는 문제이다.

 

최종 코드

#include <iostream>
using namespace std;
#define MAX 100001

int main() {
	int n, s, arr[MAX], l = 0, r = 0, sum = 0, len = 0, min = 0;
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	while (1) {
		if (sum >= s) {
			sum -= arr[l++];
			len--;
		}
		else if (r == n) break;
		else {
			sum += arr[r++];
			len++;
		}

		if (sum >= s) {
			if (min == 0 || len < min)
				min = len;
		}
	}

	cout << min << '\n';

	return 0;
}

 

이렇게 앞서 푼 문제들과 다른 점은

len이라는 변수를 추가하고, cnt 변수가 없다는 점이다.

마지막 if문에서는 최솟값을 저장하는 변수 min과 len을 비교하는 조건문도 추가해주었다.