백준 12015 가장 긴 증가하는 부분 수열1(DP) / JAVA

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

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

 

DP문제로서 작은것부터 커지는 Botton-Up 방식을 사용해보자

 

주어진 입력의 배열은 다음과 같다

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]
10	20	10	30	20	50

 

만약 arr 이 arr[0] 까지 있다면 {10} 으로 최대 길이는 1 (dp[0]=1)

거꾸로 가며(<-) 기준 수보다 작은 수를 찾아가며 길이에 + 1을 해주고 길이 중 최댓값을 dp배열에 넣는다.

dp[0]

1

arr[1] : arr[1] > arr[0] => dp[0] + 1 하여 길이는 2 (dp[1]=2)

dp[0]	dp[1]
1	2

arr[2] : arr[2] < arr[1] => 패스, arr[2] == arr[0] => 패스, 길이는 1 (dp[2]=1)

dp[0]	dp[1]	dp[2]
1	2	1

arr[3] : arr[3] > arr[2] => dp[2] + 1 = 2, arr[3] > arr[1] => dp[1] + 1 = 3,

arr[3] > arr[0] => dp[0] + 1 = 2

따라서 최대길이는 3 (dp[3]=3)

dp[0]	dp[1]	dp[2]	dp[3]
1	2	1	3

arr[4] < arr[3] => 패스, arr[4] > arr[2] => dp[2] + 1 = 2,

arr[4] == arr[1] => 패스, arr[4] > arr[0] => dp[0] + 1 = 2

따라서 최대길이는 2

dp[0]	dp[1]	dp[2]	dp[3]	dp[4]
1	2	1	3	2

arr[5] > arr[4] => dp[4] + 1 = 3, arr[5] > arr[3] => dp[3] + 1 = 4,

arr[5] > arr[2] => dp[2] + 1 = 2, arr[5] > arr[1] => dp[1] + 1 = 3,

arr[5] > arr[4] => dp[4] + 1 = 3

따라서 최대길이는 4

dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]
1	2	1	3	2	4

실제로 {10,20,30,50} 이므로 최대길이 4를 만족하는 배열 dp를 위와 같은 방식으로 구하였다.

 

아래는 dp방식(Bottom-Up) 방식으로 구현한 코드이다.

public static int dp(int[] arr) {
    int result = 0;
    int[] dp = new int[arr.length];
    resulr = dp[0] = 1; // arr 크기가 1일 경우를 대비하기위해 dp 최솟값 초기화
    for(int i = 1; i < arr.length; i++) {
        int max = 0;
        for(int j = i-1; j >= 0; j--) {
            if(arr[i] > arr[j] && dp[j] > max) {
                max = dp[j];
            }
        }
        dp[i] = max + 1;
        result = Math.max(result, dp[i]);
    }
    return result;
}

반복문을 수행하여 i 인덱스를 기준으로 삼은 배열을 거꾸로 인덱스를 감소시켜가며 크기를 비교한다

만약 크거나 같을경우 무시하고 작은 경우에만 최댓값을 해당 비교 인덱스 배열의 최대길이로 셋팅한다.

이 경우 비교 인덱스의 최대길이보다 이미 최댓값이 클 경우 도 조건을 만족시켜줘야한다.

만약 배열의 크기가 1일 경우 result 값을 계산하는 반복문을 수행하지 않으므로 최초 초기화를 해줘야한다.

 

아래는 전체 소스코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int A = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[A];
		for(int i = 0; i < A; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(dp(arr));
	}
	
	public static int dp(int[] arr) {
		int result = 0;
		int[] dp = new int[arr.length];
		dp[0] = 1;
		for(int i = 1; i < arr.length; i++) {
			int max = 0;
			for(int j = i-1; j >= 0; j--) {
				if(arr[i] > arr[j] && dp[j] > max) {
					max = dp[j];
				}
			}
			dp[i] = max + 1;
			result = Math.max(result, dp[i]);
		}
		return result;
	}
}