117221 [백준_11722] 가장 긴 감소하는 부분 수열 python 컴퓨터는 1초에 1억번까지의 연산이 가능하다고 생각하면 된다. 이는 시간복잡도를 계산할 때 유용하게 사용하는 꿀팁이다. 이 문제의 경우 n이 1000개까지 입력되므로, n 제곱까지의 시간복잡도는 허용된다고 생각하면 된다. # n 입력 n = int(input()) # a 입력 a = list(map(int, input().split())) # dp 설계 dp = [ 0 for _ in range(n) ] # dp 초기설정 dp[0] = 1 # 점화식 활용, dp 채워넣기 for i in range(1, n): # 최댓값 설정 M = 0 # i-1 까지 탐색하면서 for j in range(i): # a[i] 보다 크고, 현재 최댓값보다 dp값이 크다면, if a[j] > a[i] and dp[j] > M.. 2022. 7. 9. 이전 1 다음
