https://www.acmicpc.net/problem/1946
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 정렬을 이용해서 풀 수 있었던 그리디 알고리즘 문제입니다. 문제를 잘 읽어보면 어떤 사람을 탈락시켜야 하는지 어떤 사람을 선발할 수 있을지에 대해서 알 수 있습니다. 예를 들어 다음의 경우가 있다고 생각해봅시다.
(3, 4)
(2, 1)
(1, 3)
(4, 2)
이 경우 서류심사 성적을 기준으로 오름차순을 취하면 다음과 같이 정렬됩니다.
(1, 3)
(2, 1)
(3, 4)
(4, 2)
문제에서 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠으므로 (3, 4), (4, 2)인 사람은 서류심사 성적, 면접시험 성적 모두 (2, 1)에 비해서 떨어집니다. 따라서 이 둘을 탈락시키면 합격시킬 수 있는 사람은 (1, 3), (2,1)로 두 명입니다.
문제 해결을 위한 팁
위의 문제 해결을 위한 과정에서 보였듯이 먼저 서류심사 성적을 기준으로 정렬을 취합니다. 이렇게 뒤면 무조건 뒤에 정렬된 사람이 앞에 정렬된 사람보다 서류심사 성적이 낮기 때문에 면접 성적을 기준으로 이 사람을 합격시킬지 탈락시킬지 정할 수 있습니다. 즉 서류심사 등수를 기준으로 정렬을 수행하면 앞사람들 중 면접 등수가 높은 사람이 있다면 합격, 면접 등수가 낮은 사람이 있다면 탈락하면 되는 것입니다. 따라서 min값을 잡은 후 그 min값보다 낮은 등수의 사람은 탈락, min값보다 높은 등수의 사람은 합격을 시키면 됩니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
n = int(input())
data = []
for _ in range(n):
a, b = map(int, input().split())
data.append((a, b))
data.sort(key = lambda x: x[1])
min = data[0][0]
count = 1
for i in range(1, n):
if data[i][0] < min:
min = data[i][0]
count += 1
print(count)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 14659번: 한조서열정리하고옴ㅋㅋ(Python) (0) | 2022.01.06 |
|---|---|
| 백준 알고리즘 1080번: 행렬(Python) (0) | 2022.01.06 |
| 백준 알고리즘 11866번: 요세푸스 문(Python) (0) | 2022.01.06 |
| 백준 알고리즘 1789번: 수들의 합 (Python) (0) | 2022.01.03 |
| 백준 알고리즘 10610번: 30(Python) (0) | 2022.01.03 |