[BOJ] 11053 / 가장 긴 증가하는 부분 수열 / Python

[BOJ] 11053 / 가장 긴 증가하는 부분 수열 / Python

[BOJ] 11053 / 가장 긴 증가하는 부분 수열 / Python

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

풀이

긴 증가하는 부분 수열을 구하는 문제로 LIS 문제라고도 한다.

 

이중 for 문을 이용하여 현재 index 이전 까지의 수 중에서 현재 수보다 작은 숫자들을 찾고,

작은 수들의 부분 문제 결과 를 이용하여 현재 index 의 문제를 해결 할 수 있다.

 

N = int(input())

nums = list(map(int, input().split()))
dp = [1] * N

for i in range(N):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j]+1)
        
print(max(dp))

 

부문 문제 해결의 결과로 전체 문제를 해결하는 생각이 중요하다.