b14002. 가장 긴 증가하는 부분수열 4

 

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

 

 

 

📌 자바(Java)로 푸는 가장 긴 증가하는 부분수열 4 - 백준 14002 📈

최장 증가 부분 수열(LIS)을 구하고, 해당 수열을 출력하라!

🔎 문제 개요

 

백준 14002번 - 가장 긴 증가하는 부분 수열 4 문제는

기본적인 LIS(최장 증가 부분 수열) 문제에

👉 “LIS 경로까지 출력”이 추가된 버전입니다.

---

💡 예제 입력

6  
10 20 10 30 20 50

 

💡 예제 출력

4  
10 20 30 50

 

---

🛠 알고리즘 접근 방식

 

이 문제는 기본 LIS 문제에서

“LIS의 경로를 저장”해야 하기 때문에

✔ 단순한 DP 배열뿐 아니라

✔ prev[] (이전 인덱스), lastIndex[] (길이별 마지막 인덱스) 추적이 필요합니다.

 

---

🔹 핵심 구현 설명

📌 배열 구조

int[] arr = new int[N];      // 입력 수열
int[] list = new int[N + 1]; // LIS 수열 (값 기준)
int[] dp = new int[N];       // arr[i]가 LIS의 몇 번째에 있는지
int[] prev = new int[N];     // LIS 경로 추적용 이전 인덱스
int[] lastIndex = new int[N];// 길이별 마지막 인덱스

 

• list: 실제 LIS를 담지는 않지만, 값 기준으로 추적
• dp[i]: arr[i]가 LIS에서 몇 번째 위치인지
• prev[i]: 경로 추적용 포인터
• lastIndex[len]: 해당 길이에서의 마지막 인덱스

---

📌 LIS 로직

if (val > list[top]) {
    list[++top] = val;
    dp[i] = top + 1;
    prev[i] = lastIndex[top - 1];
    lastIndex[top] = i;
}

✔ 증가하는 경우, list의 뒤에 값을 추가

✔ 이전 인덱스 추적 (prev[i])

✔ 해당 길이의 마지막 위치 갱신

📌 이진 탐색으로 갱신

int left = 0, right = top;
while (left < right) {
    int mid = (left + right) / 2;
    if (list[mid] >= val)
        right = mid;
    else
        left = mid + 1;
}

✔ val을 대체할 위치를 찾아서

✔ LIS를 갱신 (길이는 유지)

 

 

📌 LIS 길이 및 수열 출력

System.out.println(top + 1);
LinkedList<Integer> result = new LinkedList<>();
int idx = lastIndex[top];
while (idx != -1) {
    result.addFirst(arr[idx]);
    idx = prev[idx];
}

✔ lastIndex[top]부터 prev[]를 따라가며 경로를 구성

✔ 정답 수열을 역추적 → 앞에서부터 출력

---

🏆 정리

✅ 핵심 포인트

• LIS에서 단순 길이 뿐만 아니라 구성 경로 추적이 필요한 문제
• prev[], lastIndex[] 활용하여 경로까지 복원
• 이진 탐색 기반 LIS (O(N log N)) + 역추적으로 해결

처음 dp와 prev 배열 없이 시도하려했으나 역추적이 없으면 정확한 구성경로 가 나오지않아 시간이 많이 끌렸습니다.

이 문제는 LIS 계열 중에서도 출력까지 필요한 확장형 문제로 실전 대비/연습용으로 아주 좋은것 같습니다 😊