[BOJ] 11053 가장 긴 증가하는 부분 수열 (Pyhton / 파이썬)

🧷 문제

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다.

🛠 풀이

이 문제는 DP로 해결할 수 있는 보편적인 문제 중 하나이다.

Step 1.
 먼저 DP table을 길이 n의 1차원 리스트로 만들어준다. 모든 부분수열은 최소한 1의 길이를 가지므로 값은 1로 초기화해준다.
d = [1] * n

Step 2.
 주어진 sequence리스트를 순회하면서 해당 인덱스 i까지 더 작은 값을 갖는 sequence[j] 중 DP table의 값이 가장 큰 d[j]에 1을 더해준다.

Step 3.
 위의 방법으로 구해진 DP table의 값들 중 가장 큰 값을 출력한다.

🖊 나의 코드

import sys

if __name__ == "__main__":
    n = int(input())
    sequence = list(map(int, input().split()))
    d = [1] * n
    for i in range(1, n):
        for j in range(i):
            if sequence[j] < sequence[i]:
                d[i] = max(d[i], d[j] + 1)

    print(max(d))