문제

이해

주어진 수열의 부분 수열 중에서 증가하는 수열을 만들고 그 중에서 가장 긴 수열의 길이를 구해야 한다.

접근

증가하는 부분 수열의 모든 경우를 구하는 것은 쉽지 않다. 따라서, 이 문제를 dp로 접근해보았다.

입력받은 수열의 크기만큼 dp 배열을 만들어 결과를 저장해보았다. 배열 dp[i]는 i가 마지막 원소로 포함될때의 수열 길이이다.

위의 예제에서 dp[0] = 1, dp[1] = 2, dp[2] = 1이 성립한다.
0에서는 원소가 하나뿐이므로 최소값인 1
1에서는 10 - 20 으로 이어지는 수열이 존재하므로 2
2에서는 이전의 원소들중에서 현재값이 제일 작기 때문에 1이 된다.

bottom-up 방식으로 dp를 구현할 때 dp[i]는 어떻게 구현할 수 있을까?
dp[i]는 i 이전의 원소 중에서 현재보다 작은 수를 찾고 그 수를 선택했을 때의 수열 길이를 저장하면 된다. 물론 이때 최장길이를 구해야 한다.

위의 예제에서 dp[5]를 구한다고 가정하자. 그렇다면 0~4까지의 원소 중에서 작은 것을 찾을 수 있다. (0, 1, 2, 3, 4) 모든 원소가 50보다 작다.

0이 선택되면 dp[5] = dp[0] + 1
1이 선택되면 dp[5] = dp[1] + 1
2이 선택되면 dp[5] = dp[2] + 1
3이 선택되면 dp[5] = dp[3] + 1
4이 선택되면 dp[5] = dp[4] + 1

위의 모든 경우에서 dp[5]는 dp[3]을 선택했을 때 가장 큰 값을 가진다.
실제로, dp[3]은 {10, 20, 30}으로 이어지는 수열이다.
dp[5]가 dp[3]을 선택하면 {10, 20, 30, 50}으로 가장 긴 수열이 되는 것이다.

코드

package java_baekjoon;

import java.util.*;

public class prob11053 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];
        int[] dp = new int[N];
        int max = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < N; i++) {
            dp[i] = 1;

            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }

            if(max < dp[i]){
                max = dp[i];
            }
        }

        System.out.println(max);
    }
}

bottom-up 방식으로 코드를 작성하였고 메모이제이션을 활용했다.

위의 설명대로 dp[i]는 가능한 dp[j] 중에서 최대값 + 1을 취하게 된다.

결과