Search
Duplicate
🍋

신입 사원

주차
18
문제번호
1946
언어
C++
티어
실버
유형
그리디
nj_Blog
nj_상태
이해도
풀이
풀이 X
사람
13 more properties

Memo

시간초과를 주의합시당..

Code

제출 날짜

@5/1/2021

메모리

3704 KB

시간

532 ms
#include <algorithm> #include <iostream> #include <vector> int T, N; std::vector<std::pair<int, int>> tcase; std::vector<int> result; void output() { for(auto& i : result) std::cout << i << '\n'; } bool comp(std::pair<int, int> &a, std::pair<int, int> &b) { if (a.first == b.first) return a.second < b.second; return a.first < b.first; } void solution() { auto cnt = N, m = N; std::sort(tcase.begin(), tcase.end(), comp); for (auto i = 1; i < N; ++i) { m = std::min(m, tcase[i - 1].second); if (m < tcase[i].second) --cnt; } result.push_back(cnt); } void input() { std::cin >> T; while (T--) { std::cin >> N; tcase = std::vector(N, std::pair<int, int>()); for (auto &i : tcase) std::cin >> i.first >> i.second; solution(); } } void preset() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } int main() { preset(); input(); output(); }
C++
복사

틀린코드 ㅜㅜ (시간초과..)

#include <algorithm> #include <iostream> #include <vector> int T, N; std::vector<std::pair<int, int>> tcase; std::vector<int> result; void output() { for(auto& i : result) std::cout << i << '\n'; } bool comp(std::pair<int, int> &a, std::pair<int, int> &b) { if (a.first == b.first) return a.second < b.second; return a.first < b.first; } void solution() { int cnt = 1; std::sort(tcase.begin(), tcase.end(), comp); for (int i = 1; i < N; ++i) { auto tmp = std::max_element(tcase.begin(), tcase.begin() + i, [](const auto &lhs, const auto &rhs) {return lhs.second > rhs.second;}); if ((*tmp).second > tcase[i].second) ++cnt; } result.push_back(cnt); } void input() { std::cin >> T; while (T--) { std::cin >> N; tcase = std::vector(N, std::pair<int, int>()); for (auto &i : tcase) std::cin >> i.first >> i.second; solution(); } } void preset() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } int main() { preset(); input(); output(); }
C++
복사