[BOJ_11053 | DP] 가장 긴 증가하는 부분 수열

풀이

가장 긴 증가하는 부분 수열을 구하는 문제는 다이나믹 프로그래밍을 이용하여 해결해야 한다.

arr 배열에는 입력받은 input data의 값, 즉 수열의 값들을 저장하고

dp  배열에는 그 숫자보다 작은 증가하는 부분 수열의 최대 길이를 저장한다.

예를들어 n = 9 인 데이터가 다음과 같이 들어온다고 가정하자.

10, 15, 40, 20, 15, 50, 35, 80, 100

이 상황에서 arr[0] ~ arr[8]까지의 값은 각각 위의 값을 순서대로 저장할 것이다.

그리고 이중 포문을 돌면서 (데이터의 개수가 더 클 때에는 O(NlogN)의 시간복잡도를 갖는 알고리즘을 사용해도 된다.)

각각의 인덱스에서 그 인덱스보다 작은 최장 부분 수열의 길이+1 의 값을 dp 배열의 값으로 저장하는 것이다.

10의 dp 값은 1, 15의 dp값은 10을 확인하면서 2로 갱신

40의 dp값은 10을 확인하면서 2로 갱신, 15를 확인하면서 3으로 갱신

20의 dp값은 10을 확인하면서 2로 갱신, 15를 확인하면서 3으로 갱신

....

이 과정을 반복한 후에 dp배열의 최대값을 구해주면 가장 긴 증가하는 부분수열의 길이값을 얻어낼 수 있다.

소스 코드

import java.util.*;
public class BOJ_11053 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] arr = new int[n];
        int[] dp = new int[n];
 
        int max = 1;
        for(int i=0;i<n;i++){ arr[i] = input.nextInt(); }
        for(int i=0;i<n;i++){
            if(dp[i] == 0) dp[i] = 1;
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]) {
                    if(dp[i] < dp[j]+1)
                    {
                        dp[i] = dp[j]+1;
                        if(max < dp[i]) max = dp[i];
                    }
                }
            }
        }System.out.println(max);
 
    }
}