[Java] 백준(실버-2) 11053번 - 가장 긴 증가하는 부분 수열

문제 풀이

---

이번 문제는 동적 계획법 DP를 이용해 풀 수 있는 문제이다.

아이디어 도출

필자는 반복문을 활용한 Bottom-Up 방식이 아닌 재귀 함수를 이용한 Top-Down 방식을 이용해 풀었다.

이번 문제는 이전에 풀었던 계단 오르기와 같은 계열의 문제로써, LIS(최장 증가 부분 수열) 유형의 문제이다.

최장 증가 부분 수열(LIS)란 주어진 수열에서 오름차순으로 구성 가능한 원소들을 선택하여 최대 길이를 찾아내는 것이다. 잘 활용하면 O(N logN) 의 시간복잡도를 가진다.

예제1을 살펴보면, {10, 20, 10, 30, 20, 50}라는 수열이 주어진다. N의 크기를 가지는 arr 배열에 해당 수열을 담고 DP 테이블에 해당 위치마다의 수열 길이를 메모이제이션하는 방식으로 접근하면 된다.

1. arr[0]=10일 경우 증가 부분 수열은 arr[0]보다 이전 값이 없기에 {10}이라는 부분 수열만이 존재하여 1의 길이를 가진다. DP[0] = 1
   
2. arr[1]=20의 경우 arr[0]이 10으로 arr[1]보다 작기때문에 {10, 20}이라는 부분 수열을 만들 수 있다. DP[1] = 2
   
3. arr[2]=10의 경우, 이전 값들 중 작은 값이 없기 때문에 {10} 부분 수열을 만들 수 있다. DP[2] = 1
   …

위 과정을 N까지 반복하게 되면 D = {1, 2, 1, 3, 2, 4}라는 DP 테이블을 만들 수 있다.

DP[0] = {10} // 길이 1
DP[1] = {10, 20} // 길이 2
DP[2] = {10} // 길이 1
DP[3] = {10, 20, 30} // 길이 3
DP[4] = {10, 20} // 길이 2
DP[5] = {10, 20, 30, 50} // 길이 4

위와 같이 부분 수열들의 길이를 DP 테이블의 위치마다 갱신하면 가장 긴 부분수열의 길이는 4라는 것을 알 수 있다.

이를 DP로 어떻게 접근하여 풀 수 있을까? 아이디어를 생각해보자.

1. 일단 모든 부분 수열의 최소 길이는 1이기에 탐색시 D[N]의 값을 1로 초기화한다.
2. 0부터 N-1까지 재귀 호출하여 탐색한다.
3. 재귀 함수에서는 N-1부터 0까지 거꾸로 이전 위치까지 다시 찾아나가며, 현재의 값보다 이전 값들 중 작은 값이 있을 경우 재귀호출을 통해 작은 값이 있는 위치의 길이와 비교해가며 부분 수열의 길이를 DP 테이블에 갱신한다.
4. DP 테이블 갱신을 완료했다면, DP 테이블의 값 중 최댓값이 가장 긴 부분수열의 길이가 된다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    // DP 테이블 선언
    static int[] D;
    
    // 수열 입력 배열 선언
    static int[] arr;

    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
                
                int N = Integer.parseInt(br.readLine());

                arr = new int[N];
                D = new int[N];

                // DP 테이블의 모든 값을 -1로 초기화
                Arrays.fill(D, -1);

                // 수열 입력
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int i=0; i<N; i++) {
                    arr[i] = Integer.parseInt(st.nextToken());
                }
                
                // 0부터 N-1까지 재귀함수 호출하여 탐색
                for(int i=0; i<N; i++) {
                    recursion(i);
                }

                // DP 테이블의 최댓값을 구하기 위해 오름차순 정렬
                Arrays.sort(D);

                // DP 테이블의 마지막 원소가 최댓값이 된다.
                bw.write(D[D.length-1]+"\n");
                
        }

    }
    
    /**
     * DP 테이블을 갱신할 재귀함수
     * 
     */
    public static int recursion(int N) {
        // 방문하지 않은 위치라면
        if(D[N] == -1) {
            // 모든 부분수열의 길이는 최소 1이기에 1로 초기화
            D[N] = 1;
            /*
             * N-1부터 0까지 탐색하며 현재 값보다 작은 값을 찾는다.
             * 찾을 때, 재귀 호출을 통해 찾아온다.
             */
            for(int i=N-1; i>=0; i--) {
                if(arr[i] < arr[N]) {
                    D[N] = Math.max(D[N], recursion(i)+1);
                }
            }    
        }
        // 메모이제이션을 통해 방문한 위치의 값을 바로 반환
        return D[N];
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.