[파이썬, Python] 백준 11053: 가장 긴 증가하는 부분 수열

문제

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

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

코드

n = int(input())
num = list(map(int, input().split()))
dp = [1 for i in range(n)]

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

print(max(dp))

설명

우선 다음과 같은 메커니즘을 거치게 된다.

1. 현재 위치의 숫자(num[i])가 이전에 있는 숫자(num[j])보다 큰지 확인한다.
2. 크다면, dp[i]의 값을 dp[i]의 현재 값과 dp[j]에 1을 더한 값 중 큰 값으로 갱신한다.
(이때, j는 i보다 작은 모든 값)

10	20	10	30	20	50
1	2	1	3	2	4

1. 처음 10의 경우(i = 0) 부분수열은 자기 자신밖에 없으므로 1을 입력해 준다.

2. 20의 경우 부분수열은 {10, 20}, {20} 이 가능하므로 최대 길이인 2를 입력해 준다.

3. 2번째 10의 경우 증가하는 부분수열에 포함될 수 없으므로 초기값 1에서 변화가 없다.

4. 30의 경우 {10,20,30}, {10, 30}, {30} 등과 같이 가능하지만 이 중 최댓값인 3을 입력해 준다.
(dp[1]의 {10,20}에 30을 더한 케이스)

이러한 단계를 거친다.

최종적으로 가장 큰 dp값을 출력한다.