골드4 - 백준 1806 부분합

백준 1806 부분합

https://www.acmicpc.net/problem/1806

접근방법

문제를 보고 투 포인터를 이용해서 풀면 되겠다고 생각했다. 시작점을 첫 번째 인덱스로 가리키고 끝점을 두 번째 인덱스로 가리켜서 그 사이에 있는 합을 구하고 부분합이 S 미만이라면 끝점을 한칸 뒤로 이동해서 다음 숫자를 더해주고, S를 초과한다면 시작점을 한 칸 뒤로 이동해서 이전 숫자를 빼주는 방식으로 부분합이 S이상의 가장 짧은 수열의 사이즈를 구해주었다.

풀이

투 포인터를 구현하는데 queue를 사용해도 괜찮을 것 같아서 queue로 풀어보았다. 숫자를 입력받으면 queue에 넣어주고 sum 변수에 값을 더해주었다. while문으로 만약 sum이 S이상이라면 queue의 길이를 answer와 비교해서 갱신해주고, queue를 pop해주어 그 값을 sum에서 빼주었다.

만약 합을 만드는 것이 불가능할 경우는 0으로 초기화 되었던 answer를 그대로 출력하게 된다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

	int answer = 0;
	int N, S;
	cin >> N >> S;

	queue<int> numbers;
	int sum = 0;
	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		numbers.push(temp);
		sum += temp;

		while (sum >= S)
		{
			if (answer == 0 || numbers.size() < answer)
				answer = numbers.size();
			sum -= numbers.front();
			numbers.pop();
		}
	}

	cout << answer << endl;
	return 0;
}