78. C++ 백준 1946 번 신입 사원 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 1946 번 신입 사원 C++ 자세한 설명입니다.

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

1946번: 신입 사원

 

 

먼저 백준 1946 번 C++ 정답 코드입니다.

#include <iostream>
#define MAX 100001
using namespace std;
int grade[MAX] = {0, };

int main(){
    int T, N, a, b, rank, cnt;
    cin >> T;
    for (int t = 0; t < T; t++){
        cin >> N;
        cnt = 1;
        for (int i = 1; i <= N; i++){
            cin >> a >> b;
            grade[a] = b;
        }
        rank = grade[1];
        for (int i = 2; i <= N; i++){
            if ( grade[i] < rank ){
                rank = grade[i];
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    
    return 0;
}

 

서류 점수, 면접 점수 둘 중 하나만 남들보다 높다면 입사시키면 되므로

면접과 서류 점수를 모두 비교하여 남들보다 높은게 하나라도 있을 때 입사자 수를 1개씩 증가시키면 됩니다.

이때 점수가 아닌 ranking 으로 입력이 들어오므로

서류 점수를 index,

면접 점수를 value로 해서 입력을 받아봅시다.

그럼 자연스럽게 서류 점수순으로 정렬되어 면접 점수가 저장이 됩니다.

i 번째 지원자의 합불 여부는 어차피 서류 점수는 내림차순으로 정렬되어 있기 때문에

i - 1번째 지원자보다 어차피 낮고, 면접 점수가 높아야만 합격이 되므로

앞서 등장한 최소 면접 랭킹만 확인하여 i 번째 지원자의 랭킹이 높으면 합격입니다.

  

이제 위의 직관을 코드로 구현해봅시다.

 

cnt는 1, 

n은 입력

서류 점수를 index, 면접 점수를 value로 하는 행렬을 초기화 해줍니다.

cin >> N;
cnt = 1;
for (int i = 1; i <= N; i++){
    cin >> a >> b;
    grade[a] = b;
}

 

 

이후  지금까지의 면접점수의 최저 랭킹은 서류 점수 1등 지원자의 점수로 초기화 한 후

rank = grade[1];

 

2번 지원자부터 검사하여 커트라인보다 랭킹이 높으면 커트라인을 업데이트 하고

(이후의 지원자들은 서류 점수에서 지고 있는 상황이므로 면접 점수에서 지면 합격할 수 없음)  

합격자수를 업데이트 한 후 출력해줍니다.

for (int i = 2; i <= N; i++){
    if ( grade[i] < rank ){
        rank = grade[i];
        cnt++;
    }
}

 

C++ 백준 1946 번 신입 사원 최종 코드입니다.

#include <iostream>
#define MAX 100001
using namespace std;
int grade[MAX] = {0, };

int main(){
    int T, N, a, b, rank, cnt;
    cin >> T;
    for (int t = 0; t < T; t++){
        cin >> N;
        cnt = 1;
        for (int i = 1; i <= N; i++){
            cin >> a >> b;
            grade[a] = b;
        }
        rank = grade[1];
        for (int i = 2; i <= N; i++){
            if ( grade[i] < rank ){
                rank = grade[i];
                cnt++;
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

 

지금까지 백준 1946 번 C++ 코드와 함께 자세한 설명이었습니다.

감사합니다.