백준 11053 - 가장 긴 증가하는 부분 수열(LIS)

백준

황태건 2023. 8. 8. 23:20

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

동적계획법의 정석 문제

DP 풀이는 3가지 요소 dp식 정의, 초기값, 점화식 으로 구성된다.

처음부터 잘 할 수는 없고 꾸준히 dp문제를 풀면 감이 늘 것이다.

1) dp식 정의

dp[i] : i번째 원소까지 확인했을 때의 LIS 길이의 최댓값

2) 초기값

모든 LIS는 시작 원소를 반드시 포함하므로, 모든 원소는 최소 길이 1의 LIS에 포함된다고 할 수 있다.

따라서 dp[i] (1 <= i <= n)는 모두 1

3) 점화식

i > j인 i와 j에 대해, i번째 원소가 j번째 원소보다 클 경우 i는 j까지의 LIS의 맨 끝에 추가된다.

따라서 dp식 정의에 의해 dp[i]는 dp[j] + 1이다. 반복문을 통해 1 <= j < i인 j 중 dp[j]가 가장 큰 j를 찾으면 된다.