172161 [백준_17216] 가장 큰 감소하는 부분수열 python 이런 류의 문제에 이젠 익숙해진 기분이다. 마찬가지로 n의 범위가 1000이하이니 n^2까지의 시간복잡도는 인정해준다. # n 입력 n = int(input()) # a 입력 a = list(map(int, input().split())) # dp 설계 dp = [ 0 for _ in range(n) ] # dp 초기설정 dp[0] = a[0] # dp 채워넣기 for i in range(1, n): # 최댓값 설정 M = 0 # 이전까지 돌면서 for j in range(i): # 감소하는 수열 중 dp값이 가장 큰 것을 찾아 if a[j] > a[i] and dp[j] > M: # 최댓값 갱신 M = dp[j] # dp 넣어주기 dp[i] = M + a[i] # 출력 print(max(dp)) 2022. 7. 23. 이전 1 다음
