BOJ 1806 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

 

투 포인터를 활용해서 푸는 문제였다.

문제를 이해하는데 어려운 부분은 없었는데

 

• 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이

나는 저 S 이상이 아니라 정확히 S가 되는 것만 카운팅 되는 줄 알고 30분을 소비했다...

 

#include <iostream>
#include <algorithm>
using namespace std;

int ar[100001], n, m, s, e, sum, ans = 1e9;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> ar[i];

	while (1) {
		if (sum >= m) {
			ans = min(ans, e - s);
			sum -= ar[s++];
		}
		else if (e == n) break;
		else sum += ar[e++];
	}
	
	if (ans == 1e9) cout << 0 << endl;
	else cout << ans << endl;

	return 0;
}

 

그 외에 딱히 어려운 부분은 없었는데

while 부분을 살펴보면

 

	while (1) {
		if (sum >= m) { //sum이 찾으려는 값보다 크다면
			ans = min(ans, e - s); //그 구간의 크기값을 갱신해준다
			sum -= ar[s++]; 
		}
		else if (e == n) break;
		else sum += ar[e++];
	}

 

이런 식으로 접근하면 된다.

개인적으로 투 포인터를 활용해서 푸는 문제들은 재미있는 것 같다.