문제

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

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

나의 풀이

#dp 리스트에 저장해야 할 것: 각 배열까지 도착했을 때 만들 수 있는 가장 긴 증가하는 수열의 길이
import sys
input = sys.stdin.readline

A = int(input()) #A: 수열의 크기
B = list(map(int, input().split())) #B: 수열

dp = [0] * (A)

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

print(max(dp))

풀이 과정

문제만 보면 앞에서, 즉 작은 수에서부터 출발하여 큰 수를 만나면 수열의 크기를 늘리는 식으로 생각하기 쉽다. 하지만 해당 수의 인덱스 i에서 내려가면서 비교하는 것이 더 풀기 쉬웠던 것 같은 느낌이다.