[백준/BOJ] 백준 17979번 : What’s Mine is Mine

www.acmicpc.net/problem/17979

17979번: What’s Mine is Mine

광물 채굴 시간이 빠른 순서로 정렬한 뒤, 이전에 고른 광물이 before_selected 일 때, 고를 수 있는 광물 중 최대 수익을 구하는 함수를 만들어서 전체 최대 수익을 구했다.

 

코드

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

int m, n;
vector<int> cost(101);
vector<pair<pair<int, int>, int>> mine;
vector<int> cache(10000, -1);

//이전에 고른 광물이 before_selected 일때, 그 이후의 광물들 중 최대 수익을 구한다
int Solve(int before_selected)
{
	//더이상 고를 수 있는 광물이 없을때 (이전에 골랐던 광물이 마지막것을때)
	if (before_selected == mine.size() - 1)
		return 0;

	int& ret = cache[before_selected + 1];

	if (ret != -1)
		return ret;

	ret = 0;

	//이전에 골랐던것 다음 것들이면서 범위가 고를 수 있는 광물일때 최대 수익을 구한다
	for (int i = before_selected + 1; i < mine.size(); i++)
	{
		if (before_selected == -1 || mine[before_selected].first.second <= mine[i].first.first)
			ret = max(ret, cost[mine[i].second] * (mine[i].first.second - mine[i].first.first) + Solve(i));
	}

	return ret;
}

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

	int c;
	int s, e, t;
	cin >> m >> n;

	for (int i = 1; i <= m; i++)
	{
		cin >> c;
		cost[i] = c;
	}

	for (int j = 0; j < n; j++)
	{
		cin >> s >> e >> t;
		mine.push_back(make_pair(make_pair(s, e), t));
	}

	//시작시간이 빠른 순으로 광물 정렬
	sort(mine.begin(), mine.end());

	cout << Solve(-1);

	return 0;
}