[BOJ] 1946

me

나.. 아직도 dp랑 그리디랑 헷갈리는 것 같다.
정신체리...

'''
그리디
서류 성적을 기준으로 정렬
면접 서류 성적이 높으면 제외
'''
import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())
    newones=[list(map(int,input().split())) for _ in range(N)]
    newones.sort()
    dp=[[]]*N
    dp[0]=[newones[0]]
    for i in range(1,N):
        dp[i] = dp[i-1]
        if dp[i-1][-1][1] > newones[i][1]:
            dp[i].append(newones[i])
        # else: # 왜 이걸 넣으면 틀릴까?
        #     if len(dp[i-1])==1:
        #         dp[i]=[newones[i]]
    print(len(dp[N-1]))

others

import sys

T = int(input()) #테스트케이스

for i in range(0,T):
    Cnt = 1
    people = []
    
    N = int(input())
    for i in range(N):
        Paper, Interview = map(int,sys.stdin.readline().split())
        people.append([Paper, Interview])

    people.sort() # 서류 기준 오름차순 정렬
    Max = people[0][1]
    
    for i in range(1,N):
        if Max > people[i][1]:
            Cnt += 1
            Max = people[i][1]

    print(Cnt)

• 개수만 세기
• 어차피 마지막 사람만 비교해도 되니 다 저장하지 않고 마지막 사람만 저장해두기

출처