백준 알고리즘 11053 가장 긴 증가하는 부분 수열

안녕하세요. 전상수 입니다.

오늘도 DP문제 중에서 쉬운 문제에 속하는 문제를 풀어보겠습니다.

문제를 보면 수열 A가 있을때 가장긴 증가하는 수열의 길이를 구하는 문제입니다.

예를 들어 10, 20, 30, 40, 5, 6, 7, 8, 9, 10 이라는 수열이 있을 때 5,6,7,8,9,10 이 가장긴 증가하는 수열이 됩니다. 그래서 답은 6이 됩니다. 왜그런지 따로 설명은 필요없겠죠?

그럼 문제를 풀어보겠습니다.

예를 들어 풀어보면 10, 20, 10, 30, 20, 50 수열의 경우 50의 가장긴 증가하는 수열의 길이는

10, 20, 10, 30, 20( 50보다 작은 값 중에서 ) 중 가장 긴 증가하는 수열에서 + 1 을 한값과 같습니다.

수열을 arr 로 저장하고, 해당하는 인덱스에 가장긴 증가하는 수열의 길이를 DP로 저장하겠습니다.

이걸 식으로 나타내면 DP[n] = max(DP[n - 1] , DP[n - 2], DP[n - 3] , ..... , DP[1]) + 1 입니다.( arr[n-1] < arr[n] ,  arr[n-2] < arr[n], ... ,arr[1] < arr[n] 와 같이 수열의 값이 arr[n] 보다 작을때 입니다.)

코드는 아래와 같습니다.

주의 할 점을 보면
1. 수열의 마지막 수가 가장 긴 길이를 갖지 않는다.
2. 10, 20, 10, 30, 20, 50 에서 3번째 10처럼 이전 인덱스에 더 작은 값이 없는 경우 DP[인덱스]는 1을 가진다.

입니다.

감사합니다.