[ boj : 2457 ] 공주님의 정원

www.acmicpc.net/problem/2457

2457번: 공주님의 정원

문제 : 꽃들이 피고 지는 시점이 주어지고 3월1일부터 11월30일까지 1번 이상 꽃들을 피게 하고 싶을때 총 몇개의 꽃들이 최소로 필요한가?

 

해설 : 좀 갸우뚱 하는 문제였습니다. 어떤 기준으로 꽃들을 선택해야지만 최적의 값을 구할 수 있을지....

분류에서는 그리디로 나와있지만 전 DP로 풀었습니다.

 

꽃의 시작시점이 가장 빠른 순으로 정렬을 해준다음 하나씩 최소값을 갱신해 주면 됩니다.

 

정의 : DP[i] = 3월1일부터 i 일까지 꽃들이 매일 펴있을때 사용되는 꽃의 개수의 최소값

점화식 : dp[i] = min(dp[i],dp[꽃의 시작 시점 - 1])

 

이때 주의할 점은 3월1일 전의 정보들은 전부 0으로 만들어줘야 한다는 것입니다. 이유는 3월1일 전부터 피어왔던 꽃이 존재한 상태에서 3월1일부터 시작하는 꽃이 존재하면 사실 1개의 꽃으로만으로도 3월1일부터 시작할 수 있지만 2개의 꽃으로 판단해버리는 현상이 발생할 수 있기 때문입니다.

#include <bits/stdc++.h>

using namespace std;

const int INF = (int)1e9;
int dp[2000];
vector<pair<int, int>> v;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	int a, b;
	string x, y, z, k;
	cin >> n;
	for (int i = 0; i < 2000; i++)dp[i] = INF;
	for (int i = 0; i < n; i++) {
		cin >> x >> y >> z >> k;
		if (x.length() == 1)x = '0' + x;
		if (y.length() == 1)y = '0' + y;
		if (z.length() == 1)z = '0' + z;
		if (k.length() == 1)k = '0' + k;
		a = stoi(x + y);
		b = stoi(z + k);
		v.push_back({ a,b });
	}
	sort(v.begin(), v.end());
	dp[v[0].first - 1] = 0;
	for (auto u : v) {
		for (int i = u.first; i < u.second; i++) {
			if (i < 301)dp[i] = 0;
			else dp[i] = min(dp[i], dp[u.first - 1] + 1);
		}
	}
	int ans = dp[1130];
	for (int i = 301; i <= 1130; i++)
		if (dp[i] == INF || dp[i] == 0) {
			ans = 0;
			break;
		}
	cout << ans;
	return 0;
}