(BOJ) 1946 신입 사원

문제: https://www.acmicpc.net/problem/1946

문제 풀이:

- vector에 입력받은 값을 넣는다  -> v.push_back({ 서류, 면접 });

- 순위가 높은 순으로 sort

- v[0]은 서류 성적이 1위이므로 면접 점수와 관계없이 선발 가능하다.  -> cnt++, m=v[0].second (v[0] 사람의 면접 점수)

  v[1]인 사람은 v[0]인 사람보다 서류 점수가 낮기 때문에 선발되려면 v[0]인 사람의 면접 점수보다 높아야 한다.

즉, 서류 성적이 좋은 순으로 본다고 했을 때, 앞 번호인 사람들의 최소 면접 점수보다 높아야만 선발 가능

-> 사람들을 선발할수록 현재까지 최대 면접 점수 (m)은 점점 커지므로 계속 갱신시켜준다.

소스코드:

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#define inf 100001

using namespace std;

int tc,n;

int main() {

ios::sync_with_stdio(false);

cin.tie(NULL), cout.tie(NULL);

cin >> tc;

while (tc--) {

cin >> n;

vector<pair<int, int>> v;

int cnt = 1;

for (int i = 0; i < n; i++) {

int a, b;

cin >> a >> b;

v.push_back({ a,b });

}

sort(v.begin(), v.end());

int m = v[0].second;

for(int i=1;i<n;i++){

if (v[i].second < m) {

cnt++;

m = v[i].second;

}

}

cout << cnt<<'\n';

}

return 0;

}