Difference between r1.1 and the current
@@ -5,6 +5,8 @@
= 참가자 =
* 15이원준
* 박인서
== 15이원준 ==
{{{
@@ -40,12 +42,45 @@
}
}}}
== 박인서 ==
== 곽정흠 ==
= 아이디어 =
== 15이원준 ==
* 겹치는 시간 중에서 가장 먼저 끝나는 것을 기준으로 골랐습니다.
== 박인서 ==
== 곽정흠 ==
}}}
== 박인서 ==
{{{
#include <iostream>
#include <vector>
#include <algorithm>
typedef std::pair<int, int> pair_int;
std::vector<pair_int> meet;
int main()
{
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
int t1, t2;
std::cin >> t1 >> t2;
meet.push_back(pair_int(t1, t2));
}
std::sort(meet.begin(), meet.end(), [](pair_int t1, pair_int t2){
return (t1.second == t2.second ? t1.first < t2.first: t1.second < t2.second); });
int time = 0, cnt = 0;
for (int i = 0; i < n; i++) {
if (meet[i].first < time) continue;
time = meet[i].second;
cnt++;
}
std::cout << cnt;
return 0;
}
}}}
== 곽정흠 ==
= 아이디어 =
== 15이원준 ==
* 겹치는 시간 중에서 가장 먼저 끝나는 것을 기준으로 골랐습니다.
* Greedy이다.
* 위의 원준이 아이디어와 동일하다.
== 곽정흠 ==
3.1. 15이원준 ¶
#include<iostream> #include<map> #include<utility> using namespace std; int main(){ int N, ans = 0; multimap<int, int, less<int>> arr; cin>> N; for(int i = 0; i<N; i++){ int tmp1, tmp2; scanf("%d %d", &tmp1, &tmp2); arr.insert(pair<int, int>(tmp1, tmp2)); } for(auto it = arr.begin(); it != arr.end();){ int firstfinish = it->second; for(it++; it != arr.end() && it->first < firstfinish; it++){ int etime = it->second; if(etime < firstfinish){ firstfinish = etime; } } ans++; } cout<< ans << endl; }
3.2. 박인서 ¶
#include <iostream> #include <vector> #include <algorithm> typedef std::pair<int, int> pair_int; std::vector<pair_int> meet; int main() { int n; std::cin >> n; for (int i = 0; i < n; i++) { int t1, t2; std::cin >> t1 >> t2; meet.push_back(pair_int(t1, t2)); } std::sort(meet.begin(), meet.end(), [](pair_int t1, pair_int t2){ return (t1.second == t2.second ? t1.first < t2.first: t1.second < t2.second); }); int time = 0, cnt = 0; for (int i = 0; i < n; i++) { if (meet[i].first < time) continue; time = meet[i].second; cnt++; } std::cout << cnt; return 0; }