CSES PS - Towers (그리디, sorting)

https://cses.fi/problemset/task/1073

sorting and searching으로 분류된 것으로 볼때, 무작위 크기를 순서대로 multiset에 넣으면서 처리하는 것에 주목하라는 의미인 듯 하다.

 

<문재설명>

큐브를 이용해서 타워를 쌓을 것이다. (큰 큐브 위에 작은 큐브를 올리거나, 새로운 타워의 기반으로 사용하거나)

n개의 큐브의 크기가 주어질 때, 모든 큐브를 사용해서 만들 수 있는 타워의 최소개수를 구해라. (반드시 입력 순서대로 처리해야 한다.)

 

<풀이>

i번째 큐브를 이용해서 타워를 쌓을 땐, 그보다 약간 큰 큐브 위에 두는 게 최적이다.

 

 

<코드>

int main() {
	FAST;
	int n; cin >> n;
	multiset<int> st;
	while (n--) {
		int a; cin >> a;
		auto it = st.lower_bound(a + 1);
		if (it == st.end()) st.insert(a);
		else {
			st.erase(it);
			st.insert(a);
		}
	}

	cout << st.size() << '\n';
}