[Algorithm] 백준 11053 - 가장 긴 증가하는 부분 수열 in python(파이썬)

💡 백준 11053: 가장 긴 증가하는 부분 수열

나에 도달하기까지 증가하는 부분 수열의 길이가 얼마인지 저장하여 가장 긴 증가하는 부분 수열의 길이를 출력

🌱 코드 in Python

알고리즘: Dynamic Programing

import sys

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
dp = [1] * n # 가장 짧은 수열의 길이도 1이기 때문에 dp배열 1로 초기화
for i in range(1, n): # 0번째 인덱스를 제외한 1번째 인덱스부터 
	for j in range(i): # 기준 인덱스 직전까지
		if num[j] < num[i] and dp[i] <= dp[j]: # 나의 전에 존재하는 수열 요소 < 나 && 나의 부분 수열 길이 < 나의 전에 존재하는 수열 요소의 부분 수열 길이 일때
			dp[i] = dp[j] + 1 # 나의 부분 수열 갱신
print(max(dp))

가장 긴 부분 수열을 찾기 위해 각 요소마다 자신의 부분 수열 길이를 저장하여야 하기 때문에
모든 요소에 대하여 자기 직전까지의 검사를 반복해야 한다

수열[i] > 수열 [x] && dp[x]가 갱신된(=부분 수열이 존재하며 현재 내 부분 수열의 길이보다 긴 경우)
dp[x] + 1로 dp[i]를 갱신해 가장 긴 dp[n] 찾을 수 있다

나보다 작으면서 dp[i] < dp[x]라는 것은 dp[x]가 무조건 1번 이상 갱신되었다는 뜻! = 증가하는 부분 수열이 존재한다!

🧠 기억하자

어떤 때에도 무엇을 기준으로 최적해를 저장할 것인가?에서 시작하면 DP문제는 실마리를 찾을 수 있는 것 같다
이번 문제는 나의 '부분 수열의 길이'가 저장해야 할 최적해였다
따라서 내 전의 요소들을 돌며 나까지 올 때 증가하는 부분 수열이 있는가?를 찾을 수 있게끔 조건식을 짜면 문제를 풀 수 있었다

DP.. 참 재밌는데 아직 어려웡..

백준 11053 바로가기