[Python] 백준 / 가장 긴 증가하는 부분 수열 / 11053번 / LIS, DP
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
6
10 20 10 30 20 50
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
4
접근 방식
-
dp 테이블을 생성하고 1로 초기화 한다
-
반복문으로 수열을 처음부터 검사한다
-
현재 수와 이전 수들을 비교한다
-
현재 수가 이전 수보다 크면 이전 수의 dp값에 1을 더해 현재 dp값과 비교하여 큰 값을 현재 dp에 넣는다
dp값은 현재 수가 끝인 부분 수열ㅇ의 최대 길이
코드
# LIS 문제라고도 부른다 Longest Increase Subsequence
# DP 풀이
n = int(input())
num_list = list(map(int,input().split()))
dp = [1] * n
for i in range(1, n):
for j in range(i):
if num_list[i] >num_list[j]:
dp[i] = max(dp[j]+1, dp[i])
print(max(dp))
Author And Source
이 문제에 관하여([Python] 백준 / 가장 긴 증가하는 부분 수열 / 11053번 / LIS, DP), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/Python-백준-가장-긴-증가하는-부분-수열-11053번-LIS-DP저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)