[백준] 동적 계획법 - 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()

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

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Arrays;
	import java.util.StringTokenizer;
	// 가장 긴 증가하는 수열 1
	public class Main {
	static int n;
	static int[] arr, dp;
	static void input() throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	arr = new int[n + 1];
	dp = new int[n + 1];
	StringTokenizer st = new StringTokenizer(br.readLine());
	for (int i = 1; i <= n; i++)
	arr[i] = Integer.parseInt(st.nextToken());
	}
	static void dp_bottom_up() {
	for (int i = 1; i <= n; i++) {
	dp[i] = 1;
	for (int j = 1; j < i; j++) {
	if (arr[i] > arr[j] && dp[i] <= dp[j]) {
	dp[i] = dp[j] + 1;
	}
	}
	}
	System.out.println(Arrays.stream(dp).max().getAsInt());
	}
	static int dp(int k) {
	if (k == 0) return 0;
	if (dp[k] == 0) {
	dp[k] = 1;
	for (int i = 1; i <= k; i++) {
	if (arr[k] > arr[i]) {
	dp[k] = Math.max(dp[k], dp(i) + 1);
	}
	}
	}
	return dp[k];
	}
	static void dp_top_down() {
	int result = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++)
	dp(i);
	System.out.println(Arrays.stream(dp).max().getAsInt());
	}
	public static void main(String[] args) throws IOException {
	input();
	// dp_top_down();
	dp_bottom_up();
	}
	}

view raw A11053.java hosted with ❤ by GitHub

반복 (Botto-Up)

재귀 (Top-Down)