[C++ 백준 문제풀이] 백준 1806: 부분합

 

>> 풀이 전략

• 부분합 알고리즘과 투 포인터 알고리즘 활용
• Int 형의 범위를 초과하지 않음
• 부분합이 S를 넘기면 Count 변수에 저장
• Count 변수는 std::min 함수를 통해 최솟값만을 저장
• S보다 부분합이 작거다 크면 Count 변수에 저장하는 동시에 Start를 +1 해줌
  • End를 +1 하게되면 길이와 부분합의 크기만 커짐.
• S보다 부분합이 작으면 End를 +1 해줌

 

#include <iostream>

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

	int n, s;
	std::cin >> n >> s;

	int list[100001] = {};
	int temp;
	for (int i{ 1 }; i <= n; i++) {
		std::cin >> temp;
		list[i] = list[i - 1] + temp;
	}

	int count = 100000001;

	int start = 1;
	int end = 1;

	while (start <= n && end <= n)
	{
		if (list[end] - list[start - 1] >= s) {
			count = std::min(count, end - start + 1);
			start++;
		}
		else {
			end++;
		}
	}

	if (count == 100000001) std::cout << 0 << "\n";
	else std::cout << count << "\n";
}