[백준, 파이썬, 1965번] 상자넣기

 

풀이

 

• 뭔가 2중 for문을 사용해야할 것 같았는데 
• 시간초과가 안날까? 생각했지만
• 2초라서 여유있게 통과 되었다.
• 그래서 해당 인덱스의 li 값보다 작을 경우 
• 해당 인덱스의 dp값과 이전 인덱스 dp값 중
• 큰 값을 현재 dp에 넣고 안쪽 for문이 종료시 
• 현재 dp에 +1 해줘 문제 해결

 

import sys

input = sys.stdin.readline

n = int(input())

li = list(map(int,input().rstrip('\n').split()))

dp = [0]*n

dp[0] = 1

for i in range(1,n):

    for j in range(i):

        if li[j] < li[i]: dp[i] = max(dp[i],dp[j])

    dp[i] += 1

print(max(dp))