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

문제

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

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

코드

import sys
input = sys.stdin.readline

a = int(input())
num = list(map(int, input().split()))

dp = [1]*a

for i in range(a):
    for j in range(i):
        if num[j] < num[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

최소 부분 수열의 길이가 1이기 때문에 dp 배열을 다 1로 초기화해준다.

num의 원소 i에 대하여 i보다 앞에 있는 원소들을 모두 확인할 때

만약 num[j] < num[i]를 만족한다면

dp[j] ( 인덱스 j까지의 증가하는 부분 수열의 최대 길이) + 1(num[i]) => dp[i]

가 되는 것이다.

 

예를 들어, 위의 예제를 살펴보면

i가 5일때 num = [10, 20, 10, 30, 20, 50]이고 dp = [1, 2, 1, 3, 2, 1] 이다.

num[i] = 50 보다 작은 인덱스 j는 0부터 4 모두 해당한다.

각각의 j 마다 dp[5] = max(dp[5], dp[4]+1)이 실행되고

결국 dp[j]가 가장 큰 dp[3]=3 에 +1한 값인 4가 dp[5]가 된다.

최종적으로 dp = [1, 2, 1, 3, 2, 4]가 되고 출력은 max(dp) = 4 이므로 4가 출력된다.