Baekjoon Training #11053

---

#11053 가장 긴 증가하는 부분 수열

import sys
input = sys.stdin.readline

n = int(input())    # 수열의 크기 입력
num_list = list(map(int,input().split()))   # 수열을 이루는 숫자 입력
# dp 리스트 생성
dp = [0 for _ in range(n)]
# 이중 for문을 이용하여 증가수열 관리
for i in range(n):
    for j in range(i):
        if num_list[i] > num_list[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
    
print(max(dp))  # 최대 증가수열의 크기 출력

이중 for문은 최대 증가수열을 찾는 알고리즘으로 이 코드의 핵심 발상이다.

우선 num_list의 i번째 인덱스의 수와  j번째 인덱스의 수의 크기를 비교한다. 이때 j는 i보다 작은 수이다.

다음으로 dp리스트에 담긴 숫자를 i번째 숫자와 j번째 숫자를 비교한다. if문의 조건에서 알 수 있듯이 num_list[i] > num_list[j] 그리고 dp[i] < dp[j]을 동시에 만족하는 경우 dp[i]를 dp[j]의 값으로 대체한다. 다음으로 외부의 for문이 돌때 마다 dp[i]에 1을 더해준다. 구조를 보면 알 수 있지만 결국 dp리스트는 해당 인덱스의 숫자까지의 각각 증가수열의 길이를 담아두는 리스트이다.

예를 들어 num_list가 {10,20,10,30,20,50}인 경우 dp에는 {1,2,1,3,2,4}이 담기게된다.

dp리스트를 완성하면 정답은 나와있고 print를 할때 max함수를 이용하여 '최대' 증가수열의 길이를 출력해주면 된다.

---