백준 11053 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
동적계획법 문제였습니다.
맨 왼쪽 숫자부터 차례로 증가하는 부분 수열의 길이를 dp배열에 저장시키고, 비교해가는 과정을 통해 접근했습니다.
처음 dp배열의 값은 1로 초기화합니다. dp배열은 증가하는 부분수열의 길이정보다 저장됩니다.
우선 해당 인덱스의 값(arr)이 비교대상 배열의 값(arr) 보다 커야하고,
비교대상 dp배열에 저장된 길이가 해당 dp배열의 값보다 클경우에만
해당 dp배열에 (비교대상 dp배열의 값 +1 )해주는 식으로 해결했습니다.
즉, 비교대상이 자신보다 증가하는 부분수열의 길이가 큰 요소일때 그 값에 +1 해주는 식입니다.
예시)
idx : 1 2 3 4 5 6
arr : 10 20 10 30 20 50
dp : 1 2 1 3 2 4
4번째 인덱스를 구하는 과정을 보면
arr[4] = 30 을 기준으로
첫번째 요소인 10은 40보다 작고 dp값은 1이어서 조건에 만족하므로 dp[4] = dp[1] + 1 => dp[4] 는 2가 됩니다.
두번째 요소인 20은 40보다 작고 dp값은 2로 조건에 만족하므로 dp[4] = dp[2] + 1 => dp[4]는 3이 됩니다.
세번째 요소인 10은 40보다 작지만 dp값이 dp[4]보다 작으므로 조건에 부합되지 않습니다.
따라서 dp[4]에는 3이 저장됩니다.