백준 1806 부분합 (C++)

안유태·2022년 7월 5일
0

알고리즘

목록 보기
2/239

1806번: 부분합

투포인터를 활용한 문제이다.
start를 기준으로 반복문을 돌며 내부 반복문에서 end를 옮기며 S보다 합이 큰 연속된 부분합의 길이를 구했다. 그 후 더 짧은 길이의 부분합을 구하기 위해 end까지 start를 옮기고 발견하면 그 길이를 구하고 이를 반복한다.
출력 조건에 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 라는 부분을 간과하여 시간을 낭비했다. 주의하자.



#include <iostream>
#include <algorithm>

using namespace std;

int N, S, res = 100001;
int A[100001];

void findRes() {
	int end = 0, sum = 0;

	for (int i = 0; i < N; i++) {
		while (sum < S && end < N) {
			sum += A[end];
			end++;
		}

		if (sum >= S) {
			res = min(res, end - i);
		}

		sum -= A[i];
	}

	if (res == 100001)
		res = 0;
}

void solution() {
	findRes();

	cout << res;
}

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

	cin >> N >> S;

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

	solution();
	
	return 0;
}
profile
공부하는 개발자

0개의 댓글