[Java] BOJ/백준 14002번 가장 긴 증가하는 부분 수열 4

[문제]

https://www.acmicpc.net/problem/14002

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

 

 

[풀이]

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

해당 문제를 풀기 이전에 백준 11053번 가장 긴 증가하는 부분 수열 문제를 풀어보는 것이 좋다.

이번 문제는 11053 문제처럼 DP를 이용해 푸는 것은 똑같지만 LIS 수열의 길이뿐 아니라 LIS 수열까지 출력해야 한다.

 

문제에 나온 예제 (10, 20, 10, 30, 20, 50)를 순차적으로 seq 배열에 담는다.

메모이제이션 기법을 이용해 LIS 길이를 담을 dp 배열을 선언하고 seq[0]보다 이전 값은 없기 때문에 LIS는 부분수열 {10}이 되어 dp[0] 값을 1로 미리 갱신해놓는다.

 

이전의 원소와 비교해야 하기 때문에 

이중 반복문은 이전의 원소와 비교해야하기 때문에 i는 1부터 N 미만까지, j는 i - 1부터 0까지 순회한다.

순차적으로 원소를 비교해 LIS의 길이를 갱신해 주고, dp[i] = Math.max(dp[i], dp[j] + 1);

가장 긴 LIS 길이를 갱신한다. maxSize = Math.max(maxSize, dp[i]);

int[] dp = new int[N];
dp[0] = 1;
int maxSize = 1;
for (int i = 1; i < N; i++) {
    dp[i] = 1;
    for (int j = i - 1; j >= 0; j--) {
        if (seq[j] < seq[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
            maxSize = Math.max(maxSize, dp[i]);
        }
    }
}

반복문을 모두 순회해 dp 배열을 갱신해서 나온 maxSize와 Stack 자료구조를 이용해 LIS 수열의 원소의 값을 Stack에 넣어준다. 

Stack<Integer> stack = new Stack<>();
for (int i = N - 1; i >= 0; i--) {
    if (dp[i] == maxSize) {
        stack.add(seq[i]);
        maxSize--;
    }
}

 

그 후 Stack에 저장된 데이터를 StringBuilder에 추가한 후 출력한다.

while (!stack.isEmpty()) sb.append(stack.pop() + " ");

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] seq = new int[N];
        for (int i = 0; i < N; i++) seq[i] = Integer.parseInt(st.nextToken());

        int[] dp = new int[N];
        dp[0] = 1;
        int maxSize = 1;
        for (int i = 1; i < N; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (seq[j] < seq[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    maxSize = Math.max(maxSize, dp[i]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(maxSize + "\n");

        Stack<Integer> stack = new Stack<>();
        for (int i = N - 1; i >= 0; i--) {
            if (dp[i] == maxSize) {
                stack.add(seq[i]);
                maxSize--;
            }
        }
        while (!stack.isEmpty()) sb.append(stack.pop() + " ");
        System.out.println(sb);
    }
}