λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
✨ Algorithm

[λ°±μ€€/C++] 1946번: μ‹ μž… 사원

by nitronium102 2022. 6. 28.

문제

μ–Έμ œλ‚˜ μ΅œκ³ λ§Œμ„ 지ν–₯ν•˜λŠ” κ΅΄μ§€μ˜ λŒ€κΈ°μ—… μ§„μ˜ μ£Όμ‹νšŒμ‚¬κ°€ μ‹ κ·œ 사원 μ±„μš©μ„ μ‹€μ‹œν•œλ‹€. 인재 μ„ λ°œ μ‹œν—˜μ€ 1μ°¨ μ„œλ₯˜μ‹¬μ‚¬μ™€ 2μ°¨ λ©΄μ ‘μ‹œν—˜μœΌλ‘œ 이루어진닀. μ΅œκ³ λ§Œμ„ 지ν–₯ν•œλ‹€λŠ” κΈ°μ—…μ˜ 이념에 따라 그듀은 졜고의 μΈμž¬λ“€λ§Œμ„ μ‚¬μ›μœΌλ‘œ μ„ λ°œν•˜κ³  μ‹Άμ–΄ ν•œλ‹€.

κ·Έλž˜μ„œ μ§„μ˜ μ£Όμ‹νšŒμ‚¬λŠ”, λ‹€λ₯Έ λͺ¨λ“  μ§€μ›μžμ™€ λΉ„κ΅ν–ˆμ„ λ•Œ μ„œλ₯˜μ‹¬μ‚¬ 성적과 λ©΄μ ‘μ‹œν—˜ 성적 쀑 적어도 ν•˜λ‚˜κ°€ λ‹€λ₯Έ μ§€μ›μžλ³΄λ‹€ 떨어지지 μ•ŠλŠ” 자만 μ„ λ°œν•œλ‹€λŠ” 원칙을 μ„Έμ› λ‹€. 즉, μ–΄λ–€ μ§€μ›μž A의 성적이 λ‹€λ₯Έ μ–΄λ–€ μ§€μ›μž B의 성적에 λΉ„ν•΄ μ„œλ₯˜ 심사 결과와 λ©΄μ ‘ 성적이 λͺ¨λ‘ 떨어진닀면 AλŠ” κ²°μ½” μ„ λ°œλ˜μ§€ μ•ŠλŠ”λ‹€.

μ΄λŸ¬ν•œ 쑰건을 λ§Œμ‘±μ‹œν‚€λ©΄μ„œ, μ§„μ˜ μ£Όμ‹νšŒμ‚¬κ°€ 이번 μ‹ κ·œ 사원 μ±„μš©μ—μ„œ μ„ λ°œν•  수 μžˆλŠ” μ‹ μž…μ‚¬μ›μ˜ μ΅œλŒ€ μΈμ›μˆ˜λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

첫째 μ€„μ—λŠ” ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 개수 T(1 ≤ T ≤ 20)κ°€ 주어진닀. 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 첫째 쀄에 μ§€μ›μžμ˜ 숫자 N(1 ≤ N ≤ 100,000)이 주어진닀. λ‘˜μ§Έ 쀄뢀터 N개 μ€„μ—λŠ” 각각의 μ§€μ›μžμ˜ μ„œλ₯˜μ‹¬μ‚¬ 성적, λ©΄μ ‘ μ„±μ μ˜ μˆœμœ„κ°€ 곡백을 사이에 두고 ν•œ 쀄에 주어진닀. 두 성적 μˆœμœ„λŠ” λͺ¨λ‘ 1μœ„λΆ€ν„° Nμœ„κΉŒμ§€ 동석차 없이 κ²°μ •λœλ‹€κ³  κ°€μ •ν•œλ‹€.

좜λ ₯

각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ— λŒ€ν•΄μ„œ μ§„μ˜ μ£Όμ‹νšŒμ‚¬κ°€ μ„ λ°œν•  수 μžˆλŠ” μ‹ μž…μ‚¬μ›μ˜ μ΅œλŒ€ μΈμ›μˆ˜λ₯Ό ν•œ 쀄에 ν•˜λ‚˜μ”© 좜λ ₯ν•œλ‹€.

 

풀이

일단 λͺ…심해야 ν•  것은....μ£Όμ–΄μ§€λŠ” 것이 μ§€μ›μž μ μˆ˜κ°€ μ•„λ‹ˆλΌ μ§€μ›μž μˆœμœ„λΌλŠ” 것이닀! 이걸 λͺ¨λ₯΄λ©΄ λ‚˜μ²˜λŸΌ μ‚½μ§ˆν•˜κ²Œ 됨

1. μ„œλ₯˜ 심사 μˆœμœ„λŒ€λ‘œ μ •λ ¬(μ˜€λ¦„μ°¨μˆœ)

2. μ„œλ₯˜ 심사 1λ“±μ˜ κ²½μš°λŠ” 이미 합격이 보μž₯λ˜μ–΄ μžˆλ‹€. λ”°λΌμ„œ μ„œλ₯˜ 심사 1λ“±μ˜ λ©΄μ ‘ μˆœμœ„λ₯Ό κΈ°μ€€μœΌλ‘œ λ‚˜λ¨Έμ§€ μ§€μ›μžλ“€μ„ ν‰κ°€ν•œλ‹€. => μ„œλ₯˜ 심사 1λ“±μ˜ λ©΄μ ‘ μˆœμœ„λ³΄λ‹€ 더 높은 μˆœμœ„μ΄λ©΄ 합격!

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> ci;

// λ‹€λ₯Έ μ§€μ›μžμ— λΉ„ν•΄ μ„œλ₯˜ 심사와 λ©΄μ ‘ μ‹œν—˜ κ²°κ³Όκ°€ λͺ¨λ‘ 떨어지면 μ„ λ°œ X
int main(){
    int T, N;
    cin >> T;

    vector<ci> people;
    for (int i=0; i<T; i++) {
        cin >> N;
        people.assign(N, {0, 0});
        for (int j = 0; j < N; j++) {
            cin >> people[j].first >> people[j].second;
        }

        // μ„œλ₯˜μ‹¬μ‚¬ μˆœμ„œλŒ€λ‘œ μ •λ ¬(μ˜€λ¦„μ°¨μˆœ)
        sort(people.begin(), people.end());

        // λ©΄μ ‘ 심사 μˆœμ„œ 확인
        int result = 1; // 기본적으둜 μ„œλ₯˜ 1등은 합격 보μž₯
        int first_order = people[0].second;
        for (int i = 1; i < N; i++){
            if (first_order > people[i].second) { // = ν‘œμ‹œ ν•„μš”X(동석차 X)
                first_order = people[i].second;
                result++;
            }
        }

        cout << result << "\n";
    }
}

λŒ“κΈ€