[백준] 11053번 가장 긴 증가하는 부분수열 (Python)

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

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

---

풀이과정

①문제 바라보기

N으로 전체 수열의 길이를 받고, 다음줄에 array가 입력된다.

array에서 몇 개의 수를 지움으로써 만들 수 있는 가장 긴 증가하는 수열의 길이를 인쇄하는 문제다.

 

②아이디어 열기

이 문제는 동적계획법으로 해결이 된다.

이중 for문을 활용하여서 해결되는 문제였다.

현재 해당하는 위치의 숫자보다 앞에 있는 숫자들이 크면 그때마다 dp[i] 값을 += 1 해주는 것이다. 그러다보면 dp[i] = array[i]가 마지막인 수열일 때 만들 수 있는 가장 긴 수열의 길이 가 된다.

 

③최종코드

N = int(input())
array = list(map(int,input().split()))
dp = [0 for _ in range(N)]
for i in range(N):
    for j in range(i):
        if array[i] > array[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))