portableangel   9년 전

서류 시험 석차 역순으로 소트한 뒤(성적이 나쁜 사람부터 좋은 사람까지)

어떤 합격자 집합을 위에서 소팅한 순서에 맞춰 뽑아놓으면 면접 시험의 석차는 감소할 수 없다(서류 시험의 석차가 더 좋은데 면접 시험의 석차마저도 더 좋을 수 없다)는 점을 이용하여

서류 시험의 석차 역순으로 소트한 뒤, 그 순서대로 보면서 면접 시험의 석차에 대한 최대 증가 수열, 즉 면접 시험의 성적이 점점 나빠지는 가장 긴 부분을 찾으면 정답이 될 줄 알았는데 아닌가 보네요 ㅠㅠ

혹시 반례가 있는 건가요? 아니면 구현이 잘못된 건가요?

h0ngjun7   9년 전

저는 오름차순(성적이 좋은 순으로)으로 정렬해서 풀었어요.

서류심사 성적 기준으로 오름차순 정렬한 다음에 순서대로 보면, 지금 현재 고려하는 녀석(A)보다 면접 성적이 우수한 애가 그전에 없었다면, 뒤에 애들에 대해서는 A보다 서류 성적이 좋은 애가 없을테고, 앞에 애들에 대해서는 A의 면접 성적이 가장 우수한 거니까 A가 답이 될 수 있다... 이런식으로 풀었어요.

성적이 나쁜 순으로 정렬을 한다면, 음... 지금 보는 A가 먼저 본 애들에 대해서는 서류성적이 좋은데... 나중에 볼 애들에 대해서는 면접성적은 모르는 거니까... 답이 명확한건가 잘 모르겠네요... 예를 들어서 다음과 같은 경우에

4

4 3

3 2

2 4

1 1

1 1이 다른 애들보다 성적이 다 월등해서 답은 1일텐데 portableangel님의 방법대로 한다면 2가 나올 거 같아요.

portableangel   9년 전

@hongjun7 감사합니다! 해결했습니다!

문제를 잘못 이해해서 1 1인 지원자같은 경우 그냥 탈락시켜버리면 고려 대상에서 제외된다고 생각해버렸네요. ㅠㅠ

덕분에 정답 받았습니다. 감사합니다~

댓글을 작성하려면 로그인해야 합니다.