PS알못 OrbitHv의 PS logo PS알못 OrbitHv의 PS

태그:

14. 동적 계획법 1 CLASS 4 ESSENTIAL

LIS를 구하는 문제입니다. DP에 사용할 배열은 길이 N짜리 배열로, 그 배열의 i번째 원소는 주어진 수열의 i번째 원소를 마지막 원소로 하는 LIS의 최대 길이를 의미합니다. i번째 원소를 구할 때는 1번째 원소부터 i-1번째 원소까지 순회하면서 i번째 원소가 LIS가 될 수 있는 경우 중 가장 길이가 긴 것을 찾습니다. 모든 원소의 값을 구하고 마지막 원소를 출력하면 됩니다.

소스 코드

언어 코드 시간
Python 3 코드(Github) / 코드(백준) 2020-03-31 23:03:19