[백준/Python] 11053 가장 긴 증가하는 부분 수열(LIS)

https://www.acmicpc.net/problem/11053

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

 

문제를 읽고 정말 단순하게 생각했다. 

 

처음 세운 조건은 1차원 배열, 그리고 해당 인덱스(array[i])와 바로 전 인덱스(array[i-1])의 배열 값을 비교하여 큰 값을 dp에 저장하는 방식이었다. 

당연히 제출 결과는 실패...^^ 

 

아래의 코드는 위의 조건을 바탕으로 작성한 코드이다. 

 

n = int(input())

array = list(map(int, input().split()))

dp = []

dp.append(array[0])

for i in range(1, n):
    if array[i-1] < array[i]:
        dp.append(array[i])
    else:
        continue

print(len(dp))

 

백준에 올라온 질문들과 반례를 넣어 다른 방식을 생각해보았으나 도저히 해결되지않아,

백준 님의 강의와 여러 블로그를 참고하였다. 

 

이 문제는 LIS(Longest Increasing Subsequence)라는 매우 유명한 문제로, 이중 for문을 이용한다. 

1. dp배열은 모두 1로 초기화한다. 

2. 현재의 인덱스(array[i])와, 안쪽 for문의 j를 이용해 처음 인덱스부터 탐색한다.

3. array[j]가 array[i]보다 작을 때, 그리고 dp[i]가 dp[j]+1보다 작을 때(또는 작거나 같을 때),

>>>이 과정의 의미는 수가 증가하고 있는지 판단 && dp에 저장할 때 최대배열수를 확인하기 위한 작업이라고 이해했다. 

4. dp[i]에 dp[j]까지의 결과 + 1을 하여 저장한다. 

5. dp배열의 최댓값을 출력! 

 

위와 같은 과정을 모두 마치면, 아래와 같은 결과가 만들어진다.

n = int(input())
array = list(map(int, input().split()))

dp = [1]*n

for i in range(n):    
    for j in range(i): 
        if array[j] < array[i] and dp[i] < dp[j]+1:
            dp[i] = dp[j]+1

print(max(dp))

 

 

백준 님의 코드와 여러 블로그를 참고하여 겨우 해결하였다. 

사실 아직도 완벽히 이해하진 못했기에 LIS관련 문제를 지속적으로 풀어볼 예정이다.