[BOJ] 11053 LIS 가장 긴 증가하는 수열

www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

1. 문제

 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

2. 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

3. 풀이

동적 계획법을 이용해 푸는 문제로 먼저 메모이제이션할 대상을 정한다. 문제에서 주어진 수열을 A, 메모이제이션 수열을 D라고 하면

D[i] : A[i]를 마지막 값으로 갖는 가장 긴 증가하는 부분수열의 길이(이후로 부턴 LIS로 표기 하겠다)

A[i]가 LIS의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 LIS의 마지막 값이 A[i]보다 작은 값이여야 한다.

 

위 문제의 예를 들어 보면

A = {10, 20, 10, 30, 20, 50} 에서

 

D[0]은 A[0]를 마지막 값으로 갖는 LIS의 길이 이므로 1 {10}   

D =[1] A=[10]

 

D[1]은 A[1]를 마지막 값으로 갖는 LIS의 길이 이므로 2 {10, 20}

D =[1, 2] A=[10, 20]

 

D[2]은 A[2]를 마지막 값으로 갖는 LIS의 길이 이므로 2 {10, 20}

D=[1, 2, 2] A=[10, 20, 10]

 

D[3]은 A[3]를 마지막 값으로 갖는 LIS의 길이 이므로 3 {10, 20, 30}

D=[1, 2, 2, 3] A=[10, 20, 10, 30]

 

즉 반복문으로 수열을 돌면서 D[i] 채워가는데

1. 수열 A에서 i 이전의 값( j < i ) 을 돌며 A[j]가 A[i]보다 작을 때

2. 현재 D[i] 값과 D[j] + 1를 비교해서 큰 값을 D[i]에 채워 넣으면 된다. 

   이런식으로 비교하는 이유는 이전까지 길이에 A[i]를 포함해야히기 때문이다. 

3. 위와 같은 방식으로 A를 한바퀴 돌고 가장 큰 값을 구하면 된다.

 

아래는 파이썬으로 푼 코드다.

N = int(input())
A=list(map(int, input().split()))

D=[1]+[0 for i in range(1,N)] 
#D 수열은 i번째 까지 왔을 때 가장 긴 증가하는 부분 수열 (LIS)

for i in range(N):
    if D[i] ==0: D[i]=1
    for j in range(i): #현재 인덱스보다 작은 j 값에 대해
        if (A[i]> A[j]): #현재 값보다 작으면 
            if(D[i]<D[j]+1): # 비교해준다.
                D[i] =D[j]+1
print(max(D))