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

[peppermintt0504]

문제 풀이

해당 문제는 DP 문제로 진행하면서 이전의 DP 중 가장 큰 값에 더해 나가며 진행하는 문제이다. 해당 문제는 DP문제로 분류되어 있지만 이분 탐색으로 푸는 문제이지만, 분류가 DP이므로 DP로 풀었다. 그렇기에 DP 문제인데도 불구하고 O(N*N)의 시간 복잡도를 가지고 있다.

위 예제의 수열은 {10, 20, 10, 30, 20, 50} 이다. 이를 seq라고 하고, dp[] 배열에 메모이제이션을 한다.

먼저 seq[0] = 10에 대한 수열을 찾아보면 seq[0]보다 이전 값은 없으므로 10 자체 하나밖에 존재하지 않으므로 dp[0] = 1 이 된다. 그 다음 seq[1] = 20에 대한 수열을 찾아보면 seq[0] = 10으로 20보다 작기 때문에 {10, 20} 이라는 부분수열이 되고, 길이는 2로 dp[1] = 2가 되는 것이다. seq[2] = 10의 경우 이전 값들 중 작은게 없으므로 {10} 하나만 되므로 dp[2] = 1이 되고.. 이런식으로 나가는 것이다.

그렇게 증가하는 수열을 구하면 다음과 같다.

즉 각 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

풀이 코드

bottom-up (본인 풀이)

import java.util.*;
import java.io.*;
public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException{
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] board = new int[T+1];
        int[] dp = new int[T+1];
        int max = 0;

        int count = 1;
        while(T-- > 0) {
            board[count] = Integer.parseInt(st.nextToken());
            count++;
        }count--;

        for(int i = 1 ; i <= count; i++) {
            dp[i] = 1;
            for(int j = 1; j <= i; j++) {
                if(board[j] < board[i] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
            if(max < dp[i])max= dp[i];
        }
        System.out.println(max);
    }

}

(참고) top-down (출처 : https://st-lab.tistory.com/137)

static int LIS(int N) {

    // 만약 탐색하지 않던 위치의 경우 
    if(dp[N] == null) {
        dp[N] = 1;  // 1로 초기화 

        // N 이전의 노드들을 탐색 
        for(int i = N - 1; i >= 0; i--) {
            // 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
            if(seq[i] < seq[N]) {
                dp[N] = Math.max(dp[N], LIS(i) + 1);
            }
        }
    }
    return dp[N];
}

(참고) 이분 탐색 (출처 : https://st-lab.tistory.com/137)

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] seq = new int[N];
        int[] LIS = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        LIS[0] = seq[0];
        int idx = 1;

        for(int i = 1; i < N; i++) {
            if(LIS[idx - 1] < seq[i]) {
                LIS[idx++] = seq[i];
            }
            else if(LIS[0] > seq[i]) {
                LIS[0] = seq[i];
            }
            else {
                int temp = Arrays.binarySearch(LIS, 0, idx, seq[i]);
                LIS[temp < 0 ? -(temp + 1) : temp] = seq[i];
            }
        }
        System.out.println(idx);
    }
}