❓11053번 : 가장 긴 증가하는 부분 수열
〽️ 문제 요약
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하면 되는 문제.
🤨 접근법
가장 긴 증가하는 부분문제(Longest Increasing Subsequences; LIS)는 DP로 풀 수 있는 가장 보편적인 문제 유형 중 하나이다. 이미 이전에 민균이의 계략 문제에서 다뤄본 적이 있다.
본 문제를 Brute-force로 앞에서 부터 접근하는 방법에서 약간 다르게 생각해 i(0≤ i ≤ N)번째 인덱스에 대해 그 이전의 인덱스 j(0 ≤ j ≤ i)들을 고려해야한다.
기본적으로 DP 배열을 default로 1로 초기화 하고, i번째 인덱스의 값에 대해 j번째 인덱스의 값이 작은 경우, dp[i]와 dp[j]+1의 값 중 큰 값을 취한다. 이는 j번째 인덱스의 값에 대해서 i번째 인덱스의 값이 ‘증가’하게 되어 증가하는 부분 수열을 이루게 됨을 의미한다.
for i in range(N):
for j in range(i):
dp[i] = max(dp[i], dp[j]+1)또한 dp[i]가 더 큰 경우에는 이미 j보다 이전의 다른 수에 의해 더 긴 증가하는 부분 수열이 만들어 지고 있음을 의미하고, dp[j]+1이 더 큰 경우는 해당 j 인덱스의 수에 의해 가장 긴 증가하는 부분 수열이 만들어지고 있음을 의미한다.
그렇기 때문에 i=N까지 순회를 마치면 DP 배열 안에는 여러가지 증가하는 부분 수열의 길이들이 뒤죽 박죽 담겨 있다. 최종적으로 dp배열의 최댓값이 가장 긴 증가하는 부분 수열이 된다.
🔡 코드
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().rstrip().split()))
dp = [1 for _ in range(N)]
for i in range(N):
for j in range(i):
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
Grow Exponentially