[백준 14002] 가장 긴 증가하는 부분 수열 4

코뉴·2022년 3월 12일

백준🍳

목록 보기

129/149

🥚문제

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

다이나믹 프로그래밍

🥚입력/출력

🍳코드

import sys
input = sys.stdin.readline

N = int(input().strip())
A = [0] + list(map(int, input().split()))

# dp[i] = 길이가 i인 증가하는 부분 수열에서 마지막 숫자가 될 수 있는 최소값
# seq[i] = 길이가 i인 증가하는 부분 수열
dp = [0]
seq = [[]]
for i in range(1, N+1):
    """
    print("i:", i)
    print("dp:", dp)
    print("sq:", seq)
    """
    if dp[-1] < A[i]:
        dp.append(A[i])
        seq.append(seq[-1] + [A[i]])
    else:
        if A[i] in dp:
            continue
        for j in range(1, len(dp)):
            # 처음으로 A[i] < dp[j]가 되는 곳에서 dp[j] = A[i]로 업데이트
            if A[i] < dp[j]:
                dp[j] = A[i]
                seq[j] = seq[j-1] + [A[i]]
                break

print(len(dp) - 1)
result = ""
for x in seq[-1]:
    result += str(x) + " "
print(result.strip())

🧂아이디어

DP, LIS

최장 증가 부분 수열의 알고리즘을 이용하여 푼다.
(이전에 관련 문제들을 몇 번 풀었는데, 아래 참고에 링크를 걸어 놓겠다.)

dp[i] = 길이가 i인 증가하는 부분 수열에서 마지막 숫자가 될 수 있는 최소값을 저장한다.

seq[i] = 길이가 i인 증가하는 부분 수열을 저장한다.

입력받은 수열 A를 순회하며(1 <= i < N+1),
dp[-1] < A[i]이면, 현재까지 만들어진 len(dp)-1길이의 수열 뒤에 A[i]라는 수를 추가할 수 있다는 의미이다.
- 따라서, dp리스트에 A[i]를 추가한다.
- seq 리스트에 seq[-1] + [A[i]] 를 추가한다.

dp[-1] >= A[i]이면
- dp 리스트 내에 A[i]와 같은 수가 있다면 skip한다.
- dp 리스트 내에 A[i]와 같은 수가 없다면 dp 리스트를 순회하며 (1 <= j < len(dp)) 처음으로 A[i] < dp[j]가 되는 인덱스 j에서
  dp[j] = A[i]로, seq[j] = seq[j-1] + [A[i]]로 업데이트한다.