BOJ - 1806번 부분합(C++)

문제 출처: https://www.acmicpc.net/problem/1806

문제 난이도

Gold 3

문제 접근법

DP로 풀었다가 아무리 해도 답이 안나왔다. 더한만큼 빼주면 되는 투포인트 알고리즘을 사용하는 거였다. 부분합으로 max값을 구할 때 써도 되고 length 구할 때도 응용될 수 있다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int res=INF;
int N, S;
int arr[100001];


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

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

	while (plusIdx >= minusIdx && plusIdx < N) {
		if (sum < S ) {
			sum += arr[++plusIdx];
		}
		else if (sum == S) {
			res = min(res, plusIdx - minusIdx+1);
			sum += arr[++plusIdx];
		}
		else {
			res = min(res, plusIdx - minusIdx + 1);
			sum -= arr[minusIdx++];
		}
	}
	if(res == INF) cout << 0;
	else cout << res << "\n";

	return 0;
}

피드백

처음에는 ++plusIdx가 아닌 plusIdx++를 했다. 근데 이렇게 짜면 답이 끝에 있을 경우 체크를 못해준다.

반례 1

10 10
1 1 1 1 1 1 1 1 1 10

답: 1

반례 2

10 10
3 3 3 3 3 3 3 3 3 3

답: 4