[백준 #11053] 가장 긴 증가하는 부분 수열 - Python

 

 

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

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

---

---

임의의 수 a, b, c에 대해, 

a -> b -> c -> ... 인 수열의 길이는 1 + (b -> c -> ... 인 수열의 길이)와 같다.

또 1 + (b -> c -> ... 인 수열의 길이)는 1 + 1 + (c -> ... 인 수열의 길이)와 같다.

 

위와 같은 방식으로 풀게 되면 아래와 같은 재귀함수가 나온다.

#index번째 숫자부터 시작하여 증가하는 수열의 최대 길이를 구하는 함수
def get_longest_seq(arr, index):

    max_seq = 1

    for i in range(index+1,n):
        if arr[index] < arr[i]:
            max_seq = max(max_seq, get_longest_seq(i)+1)
    return max_seq

 

위의 재귀함수로도 답은 나오겠지만, 반복이 많아진다는 치명적인 단점이 있다.

예를 들어 생각해보면 index가 0일 때, arr[1]부터 arr[n-1]까지의 원소들 중 상당수 원소들의 수열도 함께 고려가 된다.

이후 index가 1일 때의 값을 알고 싶다면, index가 0일 때 고려했던 경우를 또 다시 계산해야하는 낭비가 발생한다.

---

위와 같은 문제를 해결하기 위한 해결책은 DP의 memoization을 활용하는 방법이다.

해당 index 이후에 있는 원소부터 시작하는 배열의 길이를 이미 알고 있다면 굳이 다시 계산할 필요 없이 사용하면 된다.

 

맨 뒤에서부터 시작하여 arr[i]부터 시작하는 수열 길이의 최댓값을 dp_table에 저장하고, 이 저장된 값을 이용해 한 칸씩 앞으로 이동하며 수열을 구하면 된다.

 

결과적으로 출력해야하는 가장 긴 증가하는 부분 수열은 dp_table에 저장된 값 중 최댓값이다.

위에서 설명한 모든 부분을 고려한 코드는 아래와 같다.

n = int(input())

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

# 결과를 저장할 테이블
dp_table = [-1 for i in range(n)]

# 끝에서부터 거꾸로
for i in reversed(range(n)):
    # 가장 짧은 수열의 길이는 1
    max_seq = 1
    for j in range(i + 1, n):
        if arr[i] < arr[j]:
            # arr[i] -> arr[j] -> ... 인 수열의 길이는
            # arr[j] -> ... 인 수열의 길이에 1을 더한 것과 같다.
            max_seq = max(max_seq, dp_table[j] + 1)
    # 재사용할 수 있도록 dp_table에 max_seq를 저장
    dp_table[i] = max_seq

# dp_table에 있는 값 중 최댓값이 길이가 가장 긴 수열의 길이!
print(max(dp_table))