python 백준 1946 신입사원

 

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

문제 : 선발할 수 있는 신입사원의 최대 인원수

접근법

 - 최대 최소문제이며 사이클이 돌지않음

 - 그리디로 접근하였다

 - subprob의 최적의 해가 total prob의 최적의 해와 일치 한다.

 - matrix를 정렬 하였을때 a,b중 하나라도 1등인애는 맨앞에 가게 되므로 반드시 신입사원 으로 뽑힌다

 - 그리고 1등 이후의 등수들은 b의 등수가 앞선애보다 낮은 등수이기만 하면 뽑히게 된다.

1	2	3	4	5
4	3	2	1	5

import sys
sys.stdin = open('inputs.text')

n = int(sys.stdin.readline())
for _ in range(n):
    t1 = int(sys.stdin.readline())
    matrix1 = [0]*(t1+1)
    for _ in range(t1):
        a,b = map(int,sys.stdin.readline().split())
        matrix1[a] = b
    min1 = 100001
    count1=0
    for data1 in matrix1[1:]:
        if min1>data1:
            min1 = data1
            count1+=1
    print(count1)