[BOJ] 11053 : 가장 긴 증가하는 부분 수열 [DP](Python)

문제 링크

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

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

소스 코드

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

dp = [1] * n # dp 테이블 초기화

for i in range(1, n): # 2번째 원소부터
    for j in range(0, i): # 그 이전 원소들과 비교하여
        if arr[i] > arr[j]: # 이전 원소보다 크다면
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

 

해설

• 다이나믹 프로그래밍(Dynamic Programming, DP)

일반적으로 DP 문제들은 현재 시점까지의 최적값을 table에 저장하여 최종 결과도 최선의 값이 도출되도록 하는 방식입니다.

그리디(Greedy)와 굉장히 유사합니다.

단,해당 시점에서 모든 요소를 따져봐야 한다는 차이점이 있습니다.

 

이 문제가 특히 그러한데, 현재 시점을 i 라고 생각한다면 그 이전의 모든 시점 j에 대해 비교합니다.

이전에 등장했던 원소와 모두 비교하면서 현재 시점의 원소가 이전보다 크다면 값을 업데이트하는 방식을 취하고 있습니다.

 

먄약 현재 시점 i 를 기준으로 직전(i-1)이나 그 전(i-2)만 비교해도 충분하다면 점화식을 세워 간단히 풀이할 수 있겠습니다만 여기서는 조금 어렵습니다.

 

max 함수를 사용하여 값을 비교하는 부분만 조금 자세히 풀어 설명해보겠습니다.

6
10 20 10 30 20 50

예시의 입력입니다.

처음 dp 테이블은 [1, 1, 1, 1, 1, 1] 으로 초기화 되어있습니다.

첫 번째 원소는 굳이 건드릴 필요가 없으므로 range는 0이 아닌 1부터로 설정해줍니다.

 

두 번째 원소 20을 확인할 때는 직전 원소 10과 비교합니다.

20이 10보다 큰 숫자이므로 max(1, 1+1)이 됩니다.

여기서 왼쪽의 1은 원소 20이 원래 가지고 있던 값, 오른쪽은 원소 10에 해당하던 값 + 1 입니다.

dp 테이블은 [1, 2, 1, 1, 1, 1] 이 됩니다.

 

다음으로 세 번째 원소 10을 확인합니다.

1) 이때 첫 번째 원소 10과 비교해보면 더 큰 값이 아닙니다.

따라서 계산하지 않고 넘어갑니다.

2) 그리고 두 번째 원소 20과 비교해보면 더 큰 값이 역시 아닙니다.

따라서 계산하지 않고 넘어갑니다.

 

마지막으로 네 번째 원소 30을 확인합니다.

1) 첫 번째 원소 10과 비교해보면 더 큰 값입니다.

따라서 max(1, 1+1) 이 되고 여기서 왼쪽의 1은 네 번째 원소 30에 해당하는 값, 오른쪽의 1은 첫 번째 원소 10에 해당하는 값입니다.

dp 테이블은 [1, 2, 1, 2, 1, 1] 이 됩니다.

2) 두 번째 원소 20과 비교해보면 더 큰 값입니다.

따라서 max(2, 2+1) 이 되고 여기서 왼쪽의 1은 네 번째 원소 30에 해당하는 값, 오른쪽의 1은 두 번째 원소 20에 해당하는 값에 1을 더한 것입니다.

dp 테이블은 [1, 2, 1, 3, 1, 1] 이 됩니다.

3) 세 번째 원소 10과 비교해보면 더 큰 값입니다.

따라서 max(3, 1+1) 이 되고 여기서 왼쪽의 1은 네 번째 원소 30에 해당하는 값, 오른쪽의 1은 첫 번째 원소 10에 해당하는 값입니다.

dp 테이블은 [1, 2, 1, 3, 1, 1] 으로 유지됩니다.

 

이런 식으로 현재 시점 i에 대해서 이전에 등장한 원소보다 큰 값인 경우 그때의 dp 테이블에 저장된 값을 꺼내어 비교하며 현재 시점의 dp 테이블값을 업데이트하는 것입니다.