동적계획법 | 백준 11053 가장 긴 증가하는 부분 수열

 

문제

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성

수열 A = {10, 20, 10, 30, 20, 50} => {10, 20, 30, 50}

 

 

입력

• 첫째 줄 수열의 크기 N 
• 둘째 줄 수열을 이루고 있는 수들

 

출력

• 가장 긴 증가하는 부분 수열(LIS)의 길이

 

동적계획법

 

1. 문제를 부분 문제로 쪼개기

• 문제를 쪼개는 기준이 필요
• 이 문제의 경우 부분 수열의 끝나는 위치를 기준으로

부분 수열의 끝나는 위치를 어떻게 기준으로 생각했을까?

DP에서는 정답이 만들어지는 마지막 상태를 생각하는 것이 핵심

수열이 A = [10, 20, 10, 30, 20, 50] 일 때
부분 수열이 50에서 끝난다고 가정하면
1. 그 직전 원소는 50보다 작은 값이며
2. 그 직전까지 증가하는 수열이어야 함

따라서 50에서 끝나는 LIS = 50보다 앞서 있으며 작은 값으로 끝나는 LIS 중 가장 긴 것의 길이 + 1

LIS가 어디에서 끝날 지는 알 수 없음
모든 Ai(원소)에 대해 끝점을 Ai로 가정하고 LIS의 길이를 구해야 한다

 

2. 점화식 세우기

• i > j이고 A[i] > A[j]일 때
• dp[i] = max(dp[i], dp[j] +1)

3. 초기값 설정

• dp[i] = 1 (자기 자신만으로 수열을 만들 수 있을 때는 1이므로)

4. 점화식을 이용해 테이블 채우기

 

 

코드

import sys
input = sys.stdin.readline

N = int(input().strip())
A = list(map(int, input().split()))
dp = [1] * N #자기 자신만 가능한 경우 1이므로 1로 초기화

for i in range(N):
    for j in range(i): #A[i]보다 앞선 수만 확인하면 되므로
    	if A[i]>A[j]:
        	dp[i] = max(dp[i], dp[j]+1) #A[i]보다 앞서고 작은 수의 LIS 길이+1

print(max(dp))

 

 

 

동적계획법 어렵다.......................................................................