[백준] 14002 : 가장 긴 증가하는 부분 수열4 - Java

백준 문제 URL

---

문제 요약

수열이 주어질 때, 그 안에서 증가하는 부분 수열 중 가장 긴 수열의 길이와 해당 수열 자체를 구하는 문제다.

즉, 단순히 LIS의 길이뿐만 아니라, 그 수열의 실제 원소까지 출력해야 한다.
출력 형식은

LIS의 길이  
LIS에 포함된 수들

순서로 요구된다.

---

핵심 아이디어

기본적인 LIS(가장 긴 증가하는 부분 수열)는 DP로 길이를 구할 수 있지만,
이번 문제는 실제로 어떤 원소들로 만들었는지를 역추적해야 한다.

따라서 다음의 2가지 정보를 동시에 저장한다:

1. 각 위치에서의 LIS 길이 — dp[i]
2. 현재 위치(i) 이전에 연결된 인덱스 — prev[i]

arr[i]가 arr[j]보다 크다면 (j < i)

• dp[i] = dp[j] + 1 로 갱신하고
• prev[i] = j 로 기록해둔다.

이후, 가장 긴 수열이 끝나는 인덱스에서 prev 배열을 따라가며 역방향으로 수열을 복원한다.

---

DP 정의 & 점화식

dp 정의

• dp[i]: arr[i]를 마지막 원소로 가지는 가장 긴 증가하는 부분 수열(LIS)의 길이
• prev[i]: arr[i] 전에 연결된 LIS 원소의 인덱스 (없을 경우 -1)

---

초기값

• 모든 원소는 자기 자신만으로 수열을 구성할 수 있으므로
  dp[i] = 1, prev[i] = -1

---

점화식

이전 원소 중 자신보다 작은 값(arr[j] < arr[i])을 찾아,
그 중 가장 긴 수열에 나를 이어 붙인다.

if (arr[i] > arr[j] && dp[i] < dp[j] + 1)
→ dp[i] = dp[j] + 1
→ prev[i] = j

---

최종 답

dp 배열에서 가장 큰 값을 가진 인덱스를 찾아 거기서부터 prev를 역추적해 수열을 구한다.

길이는 max(dp[i]),
수열은 prev 배열을 거슬러 올라가며 복원한다.

---

전체 코드 (제출용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[n];
        int[] prev = new int[n]; // 이전 원소 인덱스 저장용
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);

        int lastIdx = 0; // LIS 마지막 인덱스 저장

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j; // 이전 인덱스 기록
                }
            }
            if (dp[i] > dp[lastIdx]) {
                lastIdx = i;
            }
        }

        // LIS 복원
        List<Integer> lis = new ArrayList<>();
        for (int i = lastIdx; i != -1; i = prev[i]) {
            lis.add(arr[i]);
        }
        Collections.reverse(lis);

        // 출력
        System.out.println(dp[lastIdx]);
        for (int num : lis) {
            System.out.print(num + " ");
        }
    }
}