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

👉 문제링크

---

---

🔸 문제 분석 🔸

• 전형적인 최장 증가 부분 수열 (LIS) 문제이다.
  • LIS의 DP 풀이는 O(n^2) 이고, 이분탐색 풀이는 O(nlogn)이다.
  • 여기서는 n이 1000이므로, DP 풀이를 사용했다.

🔸 문제 풀이 🔸

• DP 배열을 만들어 사용한다.
  • DP 배열에는 현재 인덱스를 포함해서 만들어지는 가장 긴 증가하는 부분 수열의 길이를 저장한다.
  • 배열을 순회하며, 이전 인덱스들 중 DP 배열 값의 최대값 + 1을 저장한다.
  • dp[i] = max(dp[i], dp[j] + 1)

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        Dp[] dp = new Dp[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            dp[i] = new Dp(1, 0);
        }

        // DynamicProgramming
        int maxVal = 1;
        int maxIdx = 0;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (A[j] < A[i] && dp[j].cost + 1 > dp[i].cost) {
                    dp[i].cost = dp[j].cost + 1;
                    dp[i].before = j;
                }
            }
            if (maxVal < dp[i].cost) {
                maxVal = dp[i].cost;
                maxIdx = i;
            }
        }

        // Output
        int[] ans = new int[maxVal];
        int idx = maxVal - 1;
        ans[idx--] = A[maxIdx];

        while (idx >= 0) {
            maxIdx = dp[maxIdx].before;
            ans[idx--] = A[maxIdx];
        }

        StringBuilder sb = new StringBuilder();
        sb.append(maxVal).append('\n');

        for (int i = 0; i < maxVal; i++) {
            sb.append(ans[i]).append(' ');
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static class Dp {
        int cost, before;

        public Dp(int cost, int before) {
            this.cost = cost;
            this.before = before;
        }
    }
}

🔸 코드 해석 🔸

• 가장 긴 증가하는 부분 수열의 원소들도 출력해야 하므로, 값과 이전 인덱스를 저장하는 Dp 클래스를 만들어 사용했다.
• LIS의 DP 풀이 진행하고, 이전 인덱스를 탐색해서 LIS 수열의 원소 값을 구한다.

---

🔸 end 🔸

• 기본적인 LIS의 DP 풀이 문제에서 원소 출력까지 조금 추가된 문제였다.
• LIS를 정리해둔 포스팅이 있어서 크게 어렵진 않았는데, 다시보니 이분 탐색은 기억이 잘 안난다.
• N 이 1인 경우의 처리가 미흡해서 런타임 에러가 한번 났다.