[BOJ][실1][1946] 신입사원

문제 링크

문제링크

첫 번째 풀이 : 그리디

알고리즘

두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.가 중요합니다.

pair로 입력받고 first가 서류 점수, second가 면접 점수라고 할 때 정렬을 하면 서류 점수는 무조건 1,2,3,4,5,…,N까지 정렬이 됩니다.

이제 면접 점수가 남들보다 작은 사람의 수열을 골라야 합니다. 가장 긴 내림차순 순열을 고르면 됩니다.

매 순간 arr[0,i]까지 가장 작은 면접 점수를 기록해두고, 이 값이 바뀔 때마다 수열의 길이가 늘어난다고 생각하면 됩니다.

• arr[i].first : 1 2 3 4 5 6 7
• arr[i].second : 4 5 6 2 7 1 3
• arr[0,i] min : 4 4 4 2 2 1 1

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 100'001;

pii arr[MAX];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int n, m, k;
int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc = 0;
    cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> arr[i].first >> arr[i].second;
        }
        sort(arr, arr + n);
        int ans = 1;
        int curr_min = arr[0].second;
        for (int i = 1; i < n; i++) {
            if (curr_min > arr[i].second) {
                curr_min = arr[i].second;
                ans++;
            }
        }
        cout << ans << "\n";
    }
    
    return 0;
}

Success Notice: 수고하셨습니다.