[백준] 11053: 가장 긴 증가하는 부분 수열
DP
수열의 길이가 1000까지이기 때문에 O(n^2)의 알고리즘을 사용해서 문제를 풀 수있습니다.
나무위키 참조
원소가 1개라도 부분 수열이 1이므로 DP리스트는 1로 초기화해 줍니다.
그리고 현재 비교하는 수 보다 더 작은 수 들이 왼쪽에 있다면 왼쪽에 있는 디피값에 1을 더한 값과 현재 값을 비교하여 가장 큰 값을 갱신해줍니다.
그리고 디피 값의 최댓값을 출력하면 됩니다 .import sys n = int(input()) lst = list(map(int, input().split())) dp = [1] * (n) for i in range(len(lst)): for j in range(i): if lst[i] > lst[j]: dp[i] = max(dp[i], dp[j]+1) print(max(dp))
Author And Source
이 문제에 관하여([백준] 11053: 가장 긴 증가하는 부분 수열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jinii/백준-11053-가장-긴-증가하는-부분-수열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
