[백준] 동적 계획법 - 11053: 가장 긴 증가하는 부분 수열 (Java)

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

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

문제

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

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

수열을 arr 배열에 입력받아서 가장 긴 증가하는 수열을 dp 배열에 메모이제이션 하며 해결하는 문제이다.

처음 이 문제를 보면 이해가 되지 않을 수도 있어서 예시를 준비했다.

6
10 20 10 30 20 50
// 결과: 4

위의 예는 문제의 입력 예시이다.

왜 저렇게 되는지 알아보자.

10	20	10	30	20	50
1	2	1	3	2	4

dp[0] = {10} 만 포함되므로 1이다.

dp[1] = {10, 20} 2

dp[2] = {10} 다시 10만 포함된다. 1

dp[3] = {10, 20, 30}이 포함된다. 어떻게 구하는가. i = 0부터 시작해서 i = 현재 인덱스 -1 까지 탐색을 하여 입력받은 수 중 자신보다 작은 수 중, dp 결과가 가장 큰 수를 찾는다. 0 ~ 2 사이에서 가장 큰 수는 2({10, 20})이다. 거기에 자기 자신 30을 추가해서 dp[3]의 LIS는 {10, 20, 30} 으로 총 3이 된다.

dp[4] = {10, 20} 여기도 마찬가지로 자기보다 작은수는 10뿐이다. 그리고 dp결과는 1이다. 거기에 본인을 더해주면 2가 된다.

dp[5] = {10, 20, 30, 50} 으로 4가 된다. 자기 자신인 50보다 작은 수들 중 dp 결과가 가장 큰 값은 30의 3이다. 거기에 본인인 50을 더해 길이가 4 인 수열이 된다.

결과는 dp배열의 최댓값을 구해주면 된다.

Arrays.stream(dp).max().getAsInt()

나는 스트림을 이용해서 구해보았다.

반복 (Botto-Up)

재귀 (Top-Down)