3307. 최장 증가 부분 수열 (SWEA)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이

T = int(input())
for test_case in range(1, T + 1):
    N=int(input())
    N_list=list(map(int,input().split()))
    cnt_list=[0]*N
    cnt_list[0]=1
    for i in range(1,N):
        max_cnt=1
        for j in range(i):
            if N_list[i]>=N_list[j]:
                max_cnt=max(max_cnt,cnt_list[j]+1)
        cnt_list[i]=max_cnt
    ans=max(cnt_list)
    print(f'#{test_case} {ans}')

• DP로 풀었다.
• 이전 값보다 이후의 값이 크거나 같을 때 증가수열이 유지된다.
• K번째 수는 1~K-1까지의 숫자와 비교해보아야 한다.
• 1~K-1까지 만든 증가수열 중 가장 길이가 긴 값을 선택하여 +1을 하고 저장한다.
• 최종적으로 cnt_list에서 가장 큰 값이, 가장 긴 수열 길이이다.