백준 1946 신입 사원 문제 풀이
백준 1946 신입 사원 문제 풀이
백준 온라인 저지, 1946번: 신입 사원
도입
신입 사원의 선정에 고려되는 값은 두 가지이다. 다만 이 두 가지 값을 모두 고려하면서 신입 사원을 선정하는 것은 무리가 있다.
두 값 중 하나의 값을 기준으로 정렬한다면, 순서대로 각 신입 사원을 확인하는 반복 과정에서 두 값 중 하나의 값만을 고려하는 것으로 대응할 수 있다.
서류 심사 성적을 기준으로 정렬된 목록을 가정한다. 이어서 서류 심사 성적이 가장 높은 사람부터 낮은 순으로 이어서 확인한다.
그렇다면 현재 확인하고 있는 지원자는 이전에 확인한 모든 지원자보다 항상 서류 심사 성적이 나쁘다. 현재 지원자는 이전에 확인한 모든 지원자에 대해 면접 심사 성적이 더 좋아야 한다.
이어서 현재 이후에 확인할 지원자들은 현재 지원자보다 서류 심사 성적이 더 나쁜 것이 보장된다. 현재 지원자는 이후에 확인할 모든 지원자의 성적에 대해 고려할 필요가 없다.
문제 풀이
성적 목록을 한 개의 성적을 기준으로 정렬한다. 이어서 성적 목록을 순차적으로 확인하면서, 정렬 기준으로 설정하지 않은 다른 성적에 대해 확인한다.
현재 지원자의 정렬 기준으로 설정하지 않은 성적은, 앞서 확인한 모든 지원자의 것보다 좋아야 한다. 다시 말해 앞서 확인한 모든 지원자의 최고 성적보다 좋아야 한다.
입력으로는 순위가 주어졌으므로, 앞서 확인한 모든 지원자들의 성적에서 가장 낮은 수보다 더 낮은 수여야 한다.
1
2
3
4
5
6
7
worst_s2: int
scores: list[tuple[int, int]]
for s1, s2 in scores:
if worst_s2 > s2:
passed += 1
worst_s2 = s2