[백준] 11053번 - 가장 긴 증가하는 부분 수열

 

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

 

 

 

다이나믹프로그래밍을 사용하여 해결할 수 있는 문제이다. 

 

문제에서 요구하는 것은 가장 긴 '증가하는 부분 수열'이다. 부분 수열은 연속적이지 않아도 되기 때문에 처음 문제를 접했을 때는 쉽게 풀지 못했던 기억이 있다. 이 문제를 접하기 이전의 비슷한 문제들의 경우 문제에서 어느정도의 연속성은 보장해주었기 때문이다. 

 

문제에서 주어진 예시를 보면 수열 10, 20, 10, 30, 20, 50 에서 가장 긴 증가하는 부분 수열은 10, 20, 30, 50이다.

예시에서는 운이 좋게 수열의 마지막 숫자가 최대값이어서 가장 긴 증가하는 부분 수열에 포함되었지만 경우에 따라서는 포함되지 않을 수도 있다. (10, 20, 30, 10 과 같은 수열)

이를 통해서 세워볼 수 있는 가설은 수열의 모든 요소에 대해서 해당 요소가 가장 긴 증가하는 부분 수열의 최대 값인 경우를 모두 비교해봐야 답을 구할 수 있을 것이라는 것이다.

 

문제에 주어진 조건을 통해 세운 점화식은 다음과 같다.

수열 A의 n번째요소인 A[n]가 최대값이고 LIS가 A[n]이 가장 긴 증가하는 부분 수열의 최대값을 반환할 때

만약 A[n-1] < A[n] 이라면 A[n-1] 이 최대값인 가장 긴 증가하는 부분 수열에 +1 한 값을 LIS이 반환한다. 

그러나 A[n-1] >= A[n] 이라면 A[n-2] 와 A[n]과의 관계를 비교한다. 이 과정을 수열의 첫 번째 요소까지 반복하면서 A[n]이 최대값일 때의 가장 긴 증가하는 부분 수열의 길이를 구한다.

 

위 점화식을 수열의 모든 요소들에 대하여 계산을 한다면, LIS가 재귀호출 되면서 같은 연산을 반복해야 하므로 다이나믹 프로그래밍을 사용하여 n번째 수열이 부분 수열의 최대인 경우의 부분수열의 길이를 dp[n] 에 저장한다.

 

int max = 0;
        
for (int i=1; i<=N; i++) max = Math.max(max, LIS(i));


////////////////////////////////////////////////////////////////////////////////
static int LIS (int N) {
        
    if (dp[N] == null) {
		
        // 부분수열의 최소 길이는 1이므로 dp[N]의 최소값도 1이다.
        dp[N] = 1;
        int idx = N - 1;

        while (idx > 0) {
            if (A[idx] < A[N]) 
                dp[N] = Math.max(dp[N], LIS(idx) + 1);
            idx--;
        }
    }

    return dp[N];
}

 

 

 

 

전체 코드

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

public class Main {
    
    static int[] A;
    static Integer[] dp;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        A = new int[N+1];
        dp = new Integer[N+1];
        
        dp[1] = 1;
        
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) A[i] = Integer.parseInt(st.nextToken());
        
        
        int max = 0;
        
        for (int i=1; i<=N; i++) max = Math.max(max, LIS(i));
        
        
        System.out.println(max);
        
        br.close();
    }
    
    static int LIS (int N) {
        
        if (dp[N] == null) {
            
            dp[N] = 1;
            int idx = N - 1;
            
            while (idx > 0) {
                if (A[idx] < A[N]) 
                    dp[N] = Math.max(dp[N], LIS(idx) + 1);
                idx--;
            }
        }
        
        return dp[N];
    }
}