백준 1965번 상자넣기

처음보고 진짜 어떻게 접근해야하나 싶었는데

곰곰히 생각해보니까 그냥 LIS다

n도 1000이니까 n^2 LIS로 풀면 될듯하다

 

import sys

n=int(sys.stdin.readline().rstrip())
arr=list(map(int,sys.stdin.readline().rstrip().split()))
v=[0]*n

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            v[i]=max(v[i],v[j]+1)
print(v[n-1]+1)

이왜틀...

import sys

n=int(sys.stdin.readline().rstrip())
arr=list(map(int,sys.stdin.readline().rstrip().split()))
v=[1]*n

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            v[i]=max(v[i],v[j]+1)
print(v[n-1])

아 최대개수다. 마지막요소의 개수가 아니다

import sys

n=int(sys.stdin.readline().rstrip())
arr=list(map(int,sys.stdin.readline().rstrip().split()))
v=[1]*n

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            v[i]=max(v[i],v[j]+1)
print(max(v))