[Python, 파이썬] SWEA 3307. 최장 증가 부분 수열

주어진 두 수열의 최장 증가 부분 수열(Longest Increasing Subsequence)의 길이를 계산하는 문제.

 

 

T = int(input()) # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    N = int(input()) # 수열의 길이
    A = list(map(int, input().split())) # 수열
    L = [0 for i in range(N)] # 최대 증가 수열의 길이

    for i in range(N):

        max_ = 1
        
        for j in range(i):

            if(A[j] <= A[i]): # 수열 A[j]가 작을 시
                max_ = max(L[j]+1, max_) # 최강 증가 수열의 길이 +1와 max값 비교

        L[i] = max_ # 최강 증가 수열 저장


    print("#%d %d" %(test_case, max(L)))

 

 

 

[문제풀이]

---

 

DP를 통해 푸는 문제.

L[i] = (L[i] >= L[j])중 가장 큰 L[j]+1 

 

각 위치에서의 최장 증가 수열은 이렇게 구한다.

 

현 증가 수열, L[i]를 구하기 위해선 우선 수열 A를 봐야 한다.

A[i]보다 작은 A[j]를 가진다면 그 위치 증가 수열에 현 수열의 값을 더한게 증가 수열이 된단 의미다.

 

위의 경우엔 이전 수열의 값 모두가 현 수열의 값보다 작다.

[4, 5]
[2, 3, 5]
[3, 5]
[1, 5]

 

그럼 각 위치에서의 증가 수열+A[i]하면 이렇게 된다.

이 경우 중 가장 큰 길이를 갖는게 현재 위치에서의 최장 증가 수열의 길이!

 

max(L)

 

이렇게 각 위치에서의 최장 증가 수열을 가진 배열 L을 구한 후, 그 중 최대값을 구하면 전체 배열에서의 최장 증가 수열의 길이가 된다.