[BOJ] 2457번 : 공주님의 정원

1. problem : 

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

 

2. solution1 :

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second 
int n;
pair<int, int> flowers[100005];
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string a, b, c, d;
		cin >> a >> b >> c >> d;
		if (b.length() == 1) b = "0" + b;
		if (d.length() == 1) d = "0" + d;
		flowers[i] = { stoi(a + b),stoi(c + d) };
	}
	int ans = 0; 
	int t = 301; 
	while (t < 1201) {
		int nxt = t;
		for (int i = 1; i <= n; i++) {
			if (flowers[i].X <= t && flowers[i].Y > nxt) nxt = flowers[i].Y;
		}
		if (nxt == t) {
			cout << 0 << '\n';
			return 0;
		}
		ans++; 
		t = nxt;
	}
	cout << ans << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x11/solutions/2457.cpp

basic-algo-lecture/0x11/solutions/2457.cpp at master · encrypted-def/basic-algo-lecture

greedy 하게 접근했다. 나는 기준점을 잡지 않고, greedy를 쓰려다가 꼬였다. 하지만, 이 코드에서는 기준점 t를 잡고 t를 계속 업데이트시켜 주는 형식으로 풀이를 진행했다. t를 업데이트시키는 방법은 int nxt를 두어서, 업데이트시켰다. 이때, nxt가 변하지 않았다면, 더 이상 업데이트 하지 못한다는 이야기다. 즉 , flowers [i]. X <= t && flowers [i]. Y > nxt를 만족 못한다는 이야기다. 

t는 기준시간이다. 최소한 t는 포함해야 한다. 

nxt는 갱신할 마감값이다. 갱신하기 위해서는 nxt보다는 커야 한다. 같아도 안된다. 

갱신이 되고 나면, 더 이상 nxt이전값은 신경 쓸 필요가 없다. 따라서, t = nxt가 된다.