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

문제

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

구조

dp 테이블엔 해당 숫자 이전의 숫자들과 함께 만들 수 있는 최장 부분수열의 길이를 숫자별로 넣어준다.

대소비교를 하여 현재숫자 > 이전숫자(for문을 돌림)이면

dp[i] = max(dp[i], dp[j]+1)를 해주는 이유는

dp[j]가 j번 인덱스 숫자로 만들 수 있는 가장 최장 부분수열의 길이를 담고 있기 때문이다.

예를 들어 30으로 만들 수 있는 최장 부분수열의 길이가 dp[3]에 담겨 있는데, 이때 값이 3이다.
여기엔 [10, 20, 30]이란 부분수열을 만들 수 있어 dp[3]에 3이 담겨 있는 것이다.
이때 다음에 40이라는 숫자가 현재 숫자로 들어오면, dp[3]에 3을 만드는 데 쓰인 부분 수열의 모든 값보다 현재 숫자인 40이 더 크므로 나를 포함해서
dp[3] + 1 즉, 길이가 4인 부분수열을 만들어줄 수 있는 것이다.
그 전의 수를 돌며 최장 길이를 만들어줘야 하기 때문에 max로 계속 갱신하며 최대값만을 dp테이블에 남긴다.

풀이

import sys
input = sys.stdin.readline

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

dp = [1 for _ in range(n)] # n개의 숫자에 대해 적어도 길이가 1인 부분수열은 만들 수 있으므로 1로 초기화

# num에 있는 숫자들이 자기 자신보다 인덱스가 작은 숫자들을 돌며 
# 대소비교를 하고, 각각의 숫자들로 부분수열을 만들 수 있는지 따지며
# 가장 큰 부분수열 길이를 dp 테이블에 넣어준다.

for i in range(n):
    for j in range(i): # i보다 작은 원소들을 돎
        if num[i] > num[j]: # 현재 숫자 > 이전 숫자이면 부분수열 만들 수 있음
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))