2009.06.02 12:21 neoevoke Edit
그리디로 왜 되는지 증명을 못했다...
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct wood{ int l,w; bool bigger(const wood &a) const { return (a.l>=l) && (a.w>=w); } bool operator<(const wood &a ) const { if(a.l==l) return w<a.w; return l<a.l; }; }; int main() { int t; cin >> t; while(t--) { int n; cin >> n; vector<wood> a; a.resize(n); for(int i=0;i<n;i++) cin >> a[i].l >> a[i].w; sort(a.begin(), a.end()); int cnt=0; while(a.size()>0) { vector<int> index; index.push_back(0); for(size_t i=1;i<a.size();i++) if(a[index.back()].bigger(a[i])) index.push_back(i); while(!index.empty()) { a.erase(a.begin()+index.back()); index.pop_back(); } cnt++; } cout << cnt << endl; } return 0; }
neoevoke소셜계의 김성모