[C++][백준] 부분 합(1806)

문제

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

 

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

풀이

자연수가 주어지고, 연속적인 합이 특정 조건을 만족해야 할 때 투포인터 알고리즘을 떠올릴 수 있습니다.

 

투포인터 알고리즘의 개념은 아래 포스팅에서 확인하실 수 있습니다.

vanilla-sue.tistory.com/48

[C++][백준] 수들의 합 2(2003)

 

부분합이 S 이상일 때 가장 짧은 부분합의 길이를 찾는 문제입니다.

부분합이 S 미만이라면 포인터 e를 증가시켜주고, 

부분합이 S 이상이라면 길이를 갱신해준 뒤, 포인터 s를 증가시켜줍니다. 

 

전체코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int N, S;
int arr[100010];

int main() {
	cin >> N >> S;

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

	int s = 0, e = 0, tmp = 0;
	int answer = 987654321;

	while (1) {
		if (tmp < S) {
			tmp += arr[e];
			e++;
		}
		else {
			int length = e - s;
			if (length < answer) answer = length;

			tmp -= arr[s];
			s++;
		}

		if (e > N) break;
	}

	if (answer == 987654321) answer = 0;
	cout << answer;

	return 0;
}