백준 11053번. 가장 긴 증가하는 부분 수열 (Python / 파이썬)

문제

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

---

문제 풀이

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

가장 긴 증가하는 부분 수열이란?

 주어진 수열 A에서 오름차순으로 된 부분 수열 중

길이가 가장 긴 수열을 의미합니다.

문제에 제시된 예시를 보면 의미를 더 정확하게 이해할 수 있습니다.

 

문제를 해결하기 위해 dp 배열을 별도로 만들어고 모든 값을 1로 초기화 시켜주었습니다.

dp 배열에는 증가하는 부분 수열의 길이가 저장됩니다.

 

기준 값으로부터 앞에 있는 값들이 만약 기준 값보다 작다면,

기준 값의 dp 값을 기준 값보다 작은 값들의

dp 값에 1을 더한 값 중 가장 큰 값으로 갱신 시켜줍니다.

 

이 과정을 반복하면 가장 긴 증가하는 부분 수열의 길이를 구할 수 있습니다.

---

My Code

n = int(input()) # 수열의 크기

array = list(map(int,input().split())) # 수열

dp = [1] * n # 증가하는 부분 수열의 길이를 저장

for i in range(1, n): # 기준 값
    for j in range(i): # 기준 값보다 앞에 있는 값
        if array[i] > array[j]: # 기준 값보다 작다면
            dp[i] = max(dp[i], dp[j] + 1) # 기준 값 dp 갱신

print(max(dp)) # dp의 max는 가장 긴 증가하는 부분 수열의 길이