Suhwanc

백준 1946번 신입사원

문제 링크 : https://www.acmicpc.net/problem/1946 문제 분류 - 그리디 알고리즘 풀이 우선 문제를 읽고, 지원자의 숫자 N의 제한이 10만이라는 점을 보고 빠르게 O(n^2)로 모든 지원자들을 계속해서 비교해나가는 풀이는 포기했다. 그렇다고 O(nlgn)의 방법으로 이분탐색을 하자니.. 딱히 절반 절반 줄여나갈 포인트가 생각이 안 났고 그다음 생각난 것이 아래와 같은 풀이이다. 먼저, 입력에서 각 지원자들의 성적 순위가 주어졌기 때문에 본능적으로 무언가 정렬을 해야 할 듯하다. 따라서 정렬을 하고 보니 두 성적 중 아무 성적이나 1위를 하고 있는 신입 사원은 어떻게 뽑든 반드시 선발되기 마련이다. 만약 성적이 (1, x)인 신입 사원이 선발이 되지 않았다면, 선발될 수 있는..