Search

[백준 11053] 가장 긴 증가하는 부분 수열

[백준 11053] 가장 긴 증가하는 부분 수열

LIS(Longest Increasing Subsequence) 라는 유명한 DP 문제

Tip

각각의 수열 원소를 포함하는 증가하는 부분 수열의 길이 계산
계산한 길이를 DP 테이블에 저장 후, max()함수로 가장 긴 길이 출력
점화식
if array[i] > array[j]:
d[i] = max(d[i], d[j] + 1)

나의 풀이 (재귀함수) : 결과는 잘 나오지만 오답처리.. 이유는 모르겠음

모범 답안 소스 코드

import sys si = sys.stdin.readline # n과 수열 입력 n = int(si()) array = list(map(int, si().split())) # 증가하는 부분 수열 길이를 담을 DP 테이블 d = [1] * n for i in range(n): for j in range(i): if array[i] > array[j]: d[i] = max(d[i], d[j] + 1) # 가장 긴 증가하는 부분 수열 길이 출력 print(max(d))
Python