BOJ 1946 신입 사원

입력으로 각 신입 사원 지원자들의 서류 심사 등수와 면접 시험 등수가 주어지는데, 다른 모든 지원자랑 비교해서 서류 심사 등수와 면접 시험 등수 중 적어도 하나는 다른 모든 지원자보다 떨어지지 않는(즉, 더 높은 - 동석차는 존재하지 않는다고 나와있음) 지원자를 신입 사원으로 뽑을 것이다. 이 때 신입 사원의 최대 인원을 구하는 문제이다.

결국 서류 심사 등수와 면접 시험 등수가 둘 다 모든 지원자보다 높거나 그 중 하나만 다른 모든 지원자보다 높으면 뽑는다는 것이다.

일단 문제 분류를 보니 greedy algorithm이라고 되어있다. 난 문제 분류를 보기 전에는 어떻게 풀지 전혀 생각 못했는데... 일단 문제 분류를 보고 생각해보니 두 개의 기준(서류, 면접) 중 하나만 다른 지원자 보다 높아도 뽑히는 것이므로 일단 서류를 기준으로 sorting을 해봤다. 그럼 서류 1등은 당연히 뽑힌다. 이제 서류 2등부터 살펴보기 시작하는데, 두 번째로 뽑을 사람은 무조건 서류 등수는 서류1등보다 낮다. 그러므로 면접 등수가 더 높은 사람을 뽑아야 한다. 그리고 여기서 이제 헷갈리기 시작하는데, 지금 서류 2등부터 즉 서류 등수가 높은 사람부터 보기 때문에 면접 등수가 앞에 뽑힌 사람보다 높아야할 것이고, 그럼 다음 사람보다 면접 등수가 낮으면 어떻게 할까? 걱정할 필요 없는 것이 다음 사람보다는 이미 서류 등수가 높으니 상관 없다! 즉 앞 사람들 보다는 면접 등수가 높고 뒷 사람들보다는 서류 등수가 높게 되는 것이다. 그래서 앞 사람 보다 면접 등수가 높은 사람을 뽑으면 이제 그 면접 등수가 기준이 될 것이고 점점 면접 등수가 높은 사람을 뽑아가는 것이다.

얼핏 보면 정렬한 후 최대 감소 부분수열의 길이를 구하는 것인가? 하는 생각이 들 수도 있지만 그것은 아닌 것이 조금 생각해보면... 무조건 서류1등은 뽑히기 때문에 만약 서류1등의 면접 등수가 1등이면 그냥 그 1명밖에 못뽑는다. 이렇게 서류 1등의 면접 등수부터 시작하는 최대 감소 부분수열이라고는 할 수 있겠지만...그냥 최대 감소 부분수열을 구하면 안된다.

조금 헷갈리고 내가 이 greedy 알고리즘을 증명하지는 못하지만 어느정도 이해는 한 것 같다. 일단 풀어봐야겠다. 아 그리고 시간 복잡도는 정렬하는데 O(NlogN), 위의 방법처럼 답을 구하는데 O(N)이므로 O(NlogN)으로 보면 될 것이다. 이렇게 풀어서 AC를 받았다.

그리고 다른 분들 코드를 봤는데, sorting이 없는 코드들이 꽤 있었다. dotorya님 코드를 보니까, 이해가 되었는데 sorting을 하는 대신 처음에 입력을 받을 때, 서류등수를 배열의 인덱스로 해서 입력을 받음으로써 자연스레 서류 등수 기준으로 sorting된 것이나 마찬가지가 되고, 바로 위의 방법대로 서류 1등부터 시작해서 면접 등수가 높아지는 사람들을 세면 된다.
간단하지만 멋있는 방법이다...