[백준/BOJ] 백준 15459번 : Haybale Feast

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

15459번: Haybale Feast

map을 이용한 투 포인터를 이용해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <limits>
#include <map>
using namespace std;

int n;
long long m;
vector<int> flavor; //맛
vector<int> spicy; //매움

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int f, s;

		cin >> f >> s;

		flavor.push_back(f);
		spicy.push_back(s);
	}

	int left = 0;
	int right = 0;
	long long f_sum = 0; //구간 맛의 합
	map<int, int> s_check; //[매운맛] = 개수
	map<int, int>::iterator it;
	int result = numeric_limits<int>::max();

	while (1)
	{
		//맛의 요구사항을 만족하지 못할때
		if (f_sum < m)
		{
			if (right == n)
				break;

			if (s_check.count(spicy[right]) == 0)
				s_check.insert(make_pair(spicy[right], 1));
			else
				s_check[spicy[right]]++;

			f_sum += (long long)flavor[right];
			right++;
		}

		else
		{
			it = s_check.end();
			it--;

			result = min(result, (*it).first); //구간의 가장 큰 매운맛이랑 비교

			s_check[spicy[left]]--;

			if (s_check[spicy[left]] == 0)
				s_check.erase(spicy[left]);

			f_sum -= (long long)flavor[left];
			left++;
		}
	}

	cout << result;

}