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

0. 제목

• 백준 11053 가장 긴 증가하는 부분 수열
• BOJ 11053 가장 긴 증가하는 부분 수열
• 파이썬 11053 가장 긴 증가하는 부분 수열
• Python 11053 가장 긴 증가하는 부분 수열

---

1. 문제

www.acmicpc.net/problem/11053

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

---

2. 풀이

• dp[i] : i 번째 원소까지의 가장 긴 증가하는 부분 수열의 길이
• 가장 먼저 dp의 원소들을 1로 초기화 시켜준다.
• 문제에서 주어진 arr = {10, 20, 10, 30, 20, 50} 에서 dp[0] = 1, dp[1] = 2, dp[2] = 1 이고 초기값이 1인 dp[3]을 구하고자 할 때, arr[3]인 30이 arr[0]인 10보다 크므로 max(1, dp[0]+1) = 2, 30이 arr[1]인 20보다 크므로 max(2, dp[1]+1) = 3, 30이 arr[2]인 10보다 크므로 max(3, dp[2]+1) = max(3, 2) = 3 이다. 
• 위와 같은 방법으로 dp 배열의 원소 값을 모두 구한 후 최대값을 출력해주면 된다.

 

---

3. 코드

n = int(input())
dp = [1]*1001
array = list(map(int, input().split()))
 
for i in range(1, n):
    for j in range(0, i):
        if(array[i] > array[j]):
            dp[i] = max(dp[i], dp[j] + 1)
 
print(max(dp))