[python/백준/DP] 11053 : 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열

문제

수열 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)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이

• 증가하는 문자열 = 바로 전 숫자 보다 큰지, 작은지 고려하면 됨
• dp로 해결

1. dp의 모든 길이를 1로 지정 
2. 숫자들의 크기 비교 
    인덱스 1부터 n까지 크기를 비교해 최대길이를 찾는다.

    만약 찾고있는 인덱스의 숫자보다 작은 숫자가 존재한다면, 
    dp[찾는 인덱스보다 작은 숫자 인덱스]+1을 dp[인덱스]에 추가한다.

    max값을 찾을 때 까지 0~인덱스까지 반복한다. 

위 과정을 이해하기 쉽게 나열해보면 

A = [10, 20, 10, 30, 20, 50]
dp = [1, 1, 1, 1, 1, 1]

1) dp[1] 구하기 (*dp[0]은 항상 1이다)
    A[0](10)이 A[1](20)보다 작으므로 
    dp[1] = dp[0]+1이다. 
    
현재 dp = [1, 2, 1, 1, 1]

2) dp[2] 구하기 
    A[1](20)이 A[2](10)보다 크기 때문에 증가하는 수열에 성립하지 않는다.
    따라서 위 조건은 넘어간다.

현재 dp = [1, 2, 1, 1, 1]

3) dp[3] 구하기 
    A[2](10)이 A[3](30)보다 작으므로 
    dp[3] = dp[2]+1이다.

    위 과정을 A[0]까지 반복한다.

    현재 dp = [1, 2, 1, 2, 1]
    
    A[1](20)이 A[3](30)보다 작으므로 
    dp[3] = dp[1]+1이다.
    여기서 최대 길이를 찾기 위해 현재 dp[3]과 A[1]+1한 값을 비교한다.
    만약 dp[3](2)보다 A[1]+1(3)한 값이 더 크면 
    dp[3]을 A[1]+1의 값으로 변경한다.

...

위 과정을 반복하면 증가하는 최대 길이의 수열이 도출된다.
dp = [1, 2, 1, 3, 4]
max(dp) = 4 

코드

n = int(input())

A = list(map(int, input().split()))

dp = [1]*n

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