[백준 1946] 신입 사원 (C#, C++) - soo:bak

문제 링크

1946번 - 신입 사원

설명

각 지원자는 서류 순위와 면접 순위를 하나씩 가지고 있습니다. 다른 지원자보다 두 순위가 모두 뒤처지는 지원자는 선발할 수 없을 때, 선발 가능한 최대 인원을 구하는 문제입니다.

접근법

먼저 지원자를 서류 순위 기준으로 오름차순 정렬합니다.

이제 앞에서부터 하나씩 보면서, 지금까지 나온 지원자들 중 면접 순위의 최솟값만 기억하면 됩니다. 이미 서류 순위는 현재 지원자보다 앞선 사람들만 앞에 있으므로, 현재 지원자가 탈락하는 경우는 앞선 지원자들 중 면접 순위도 더 좋은 사람이 있는 경우뿐입니다.

따라서 정렬 후 순서대로 보면서 현재 지원자의 면접 순위가 지금까지의 최솟값보다 더 좋으면 선발하고, 최솟값도 함께 갱신합니다. 반대로 면접 순위가 더 나쁘면 앞선 누군가에게 두 순위 모두 밀리므로 선발할 수 없습니다.

이 과정을 모든 지원자에 대해 반복하면 정답을 구할 수 있습니다.

---

Code

C#

using System;
using System.Text;

class Program {
  static void Main() {
    int t = int.Parse(Console.ReadLine()!);
    var sb = new StringBuilder();

    while (t-- > 0) {
      int n = int.Parse(Console.ReadLine()!);
      int[] interview = new int[n + 1];

      for (int i = 0; i < n; i++) {
        string[] parts = Console.ReadLine()!.Split();
        int doc = int.Parse(parts[0]);
        int meet = int.Parse(parts[1]);
        interview[doc] = meet;
      }

      int count = 1;
      int best = interview[1];

      for (int doc = 2; doc <= n; doc++) {
        if (interview[doc] < best) {
          count++;
          best = interview[doc];
        }
      }

      sb.AppendLine(count.ToString());
    }

    Console.Write(sb.ToString());
  }
}

C++

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;

  while (t--) {
    int n;
    cin >> n;

    vector<int> interview(n + 1);
    for (int i = 0; i < n; i++) {
      int doc, meet;
      cin >> doc >> meet;
      interview[doc] = meet;
    }

    int count = 1;
    int best = interview[1];

    for (int doc = 2; doc <= n; doc++) {
      if (interview[doc] < best) {
        count++;
        best = interview[doc];
      }
    }

    cout << count << "\n";
  }

  return 0;
}