백준) 1806 - 부분합

1806번: 부분합 (acmicpc.net)

1806번: 부분합

---

투포인터를 활용한 문제

#include <iostream>

using namespace std;

int main(void) {
	int check[100001] = {0,};
	int N, S;
	cin >> N >> S;
	
	for(int i = 0; i < N; i++) {
		cin >> check[i];
	}
	
	int shortest = N+1;
	int point_front = 0, point_back = 0;
	int sum = 0;
	
	while(point_front < N) {
		if(sum < S) {
			sum += check[point_front];
			point_front++;
		}
		else {
			if(shortest > point_front - point_back) {
				shortest = point_front - point_back;
			}
			sum -= check[point_back];
			point_back++;
		}
	}
	
	while(sum >= S && point_back < N) {
		if(shortest > point_front - point_back) {
			shortest = point_front - point_back;
		}
		sum -= check[point_back];
		point_back++;
	}
	
	if(shortest == N+1) {
		cout << "0" << endl;
	}
	else {
		cout << shortest << endl;
	}
	
	return 0;
}

배열의 두 부분을 가르키는데 먼저 나갈 포인터 하나와 나중에 따라올 포인터 하나를 설정했다.

먼저 가는 포인터는 합이 S보다 작을 경우 계속 증가할 것이고 나중에 가는 포인터는 합이 S보다 크거나 같을 경우 계속 감소하는 방법으로 답을 구해준다.

 

막 어렵지는 않았었던 문제.