10571 백준 파이썬

요약하면, 무게가 커지고, 선명도 값이 감소하는 최장수열을 구하라는 것

 

여타 다른 dp문제와 동일하되, 두가지 값을 동시에 비교한다.

반복문을 통해 0부터 n까지 기준값을 높히고, 0부터 x까지 비교값을 바꿔가며 무게와 서명도를 비교하고, 그에따라 compare 배열에 값을 바꿔준다.

출력은 compare의 최대값을 출력해주면 된다.

t=int(input())
for _ in range(t):
    n=int(input())
    compare=[1 for x in range(n)]
    w=[]
    c=[]
    for _ in range(n):
        a,b=map(float, input().split())
        w.append(a)
        c.append(b)
    for x in range(n):
        for y in range(x):
            if w[x]>w[y] and c[x]<c[y]:
                compare[x]=max(compare[x],compare[y]+1)
    print(max(compare))