[ 백준 ][ 골드4 ] 14002번 - 가장 긴 증가하는 부분 수열 4 ( 파이썬 )

링크 : https://www.acmicpc.net/problem/14002

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

 

문제

---

코드

---

n = int(input())
arr = list(map(int,input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i],dp[j]+1)

a = max(dp)
print(a)

res = []
for i in range(n-1,-1,-1):
    if dp[i] == a:
        res.append(arr[i])
        a -= 1

print(*sorted(res))

 

풀이

---

LIS(가장 긴 증가하는 부분 수열) 알고리즘에서 부분 수열 자체를 출력해야 하는 변형문제이다.

 

n이 100만으로 커지는 문제인 경우에는 이분탐색으로 해결했지만 부분 수열 자체는 출력할 수 없었다.

이번 문제에는 n이 1000이 맥시멈이고 부분 수열 자체를 출력해야 하므로 다른 방법이 필요하다.

 

| DP |

• 가장 긴 증가하는 부분수열의 길이
  • 길이는 간단하게 dp로 알 수 있다.
  • 현재 위치보다 앞에 있는 원소들 중 작은 것의 개수를 세어주면 된다.
• 가장 긴 증가하는 부분수열
  • dp[i]가 의미하는 것은 i보다 작은 인덱스 j에 대하여 가장 긴 증가하는 부분수열의 개수이다.
  • 부분수열의 개수를 기준으로 세우고 dp배열을 거꾸로 탐색하며 원소를 정답배열에 넣고 찾고자 하는 부분수열의 개수를 감소시킨다. 
  • 예를 들어, 가장 긴 증가하는 부분수열의 길이가 4인 경우에는 dp의 값이 4인 인덱스를 찾아 그 인덱스에 해당하는 arr값을 res배열에 넣는다.
  • res에는 원소 하나가 들어왔으므로 앞으로 찾아야 하는 부분수열의 길이는 3이 된다.
  • 이제는 dp의 값이 3인 인덱스를 찾아 똑같이 arr의 값을 넣는다.
  • 이 방법이 가능한 이유는 똑같은 길이가 있을 경우 아무거나 출력해도 된다는 조건이 있기 때문이다.