백준 - 1946 신입 사원 (C++, Cpp)

1. 문제소개

1-1.  요구사항

• 회사에 지원한 사원들의 서류 성적과 면접 성적이 적어도 어떤 다른 지원자보다 떨어지지 않아야 채용 가능함
• 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구해야 함

1-2.  입력값과 출력값

// 예제 입력

2 // 총 테스트 케이스 경우의 수

5 // 5명이 지원함
3 2
1 4
4 1
2 3
5 5 // 탈락

7 // 7명이 지원함
3 6 // 탈락
7 3 // 탈락 (4 2 지원자 보다 다 떨어짐)
4 2
1 4
5 7 // 탈락
2 5 // 탈락
6 1

// 예제 출력
4
3

 

• 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어짐
• 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어짐
• 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어짐
•  두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정
• 각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력

2.문제풀이

2-1.  준비물

• (1) 테스트 케이스 수, 각 테스트별 사원 수, 서류 성적, 면접 성적, 커트라인, 출력할 결과

int N; // 총 테스트 케이스 수
int M; // 테스트 케이스 별 지원자 수
int paper; // 지원자 별 서류 성적
int interview; // 지원자 별 면접 성적
int cutline; // 탈락자를 구별할 기준 점수
int res; // 출력할 결과

• (2) 서류 성적을 인덱스로 면접 성적을 값으로 저장할 벡터 + 입력 받기

vector<int> v(M + 1);

   for (int j = 0; j < M; j++)
        {
            cin >> paper >> interview;
            v[paper] = interview;
        }
        
 // 서류 1등의 면접 성적을 인덱스 1에 저장하기 위해 M+1의 크기만큼 벡터를 선언
 // 입력 받을 때 벡터의 paper 인덱스에 interview 값을 할당

• (3) 커트라인을 설정하고 결과 값을 만들어가는 로직

cutline = v[1]; // 서류 1등의 지원자의 면접 성적을 cutline으로 설정
        for (int j = 1; j <= M; j++)
        {
            if (cutline > v[j]) // 만약 지금 커트라인보다 탐색하는 지원자의 면접 등수가 높다면
            {
                res++; // 합격자에 넣어주고
                cutline = v[j]; // 그 합격자의 면접 성적을 새로운 cutline으로 설정
            }
        }

• (4) 각 케이스마다 벡터를 초기화하고 정답을 출력

       v.clear();
        cout << res << '\n';

2-2.  풀이방법

• 1) 서류 성적이 1등이라는 것은 다른 지원자보다 서류성적은 무조건 좋으므로 이 서류 1등 지원자보다 면접 성적이 낮다면,
  • 해당 지원자는 서류 1등 성적 지원자보다 서류와 면접이 등수가 더 낮은 것이므로 절대 합격할 수 없음
  • 또한 서류 1등 지원자는 어떤 지원자보다 서류 성적이 좋으므로 합격이기 때문에 res 는 1 부터 시작
• 2) 만약 서류 1등보다 면접 성적이 좋은 지원자가 발생하면 이 지원자는 합격이므로 res값을 1 늘려줌
  • 이 경우 뒤에서 탐색할 지원자들은 방금 합격한 지원자보다도 서류 성적이 낮은 지원자 이므로
  • 방금 합격한 지원자보다 면접 성적이 낮으면 불합격해야함
  • 그래서 커트라인을 이 지원자의 면접 성적으로 다시 재설정해서 반복문을 탐색

3. 전체 소스 코드

#include <iostream>
#include <vector>
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

int main()
{
    int N, M, paper, interview, cutline, res;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> M;
        res = 1;
        vector<int> v(M + 1);
        for (int j = 0; j < M; j++)
        {
            cin >> paper >> interview;
            v[paper] = interview;
        }
        cutline = v[1];
        for (int j = 1; j <= M; j++)
        {
            if (cutline > v[j])
            {
                res++;
                cutline = v[j];
            }
        }
        v.clear();
        cout << res << '\n';
    }
}