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

📖 문제

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

 

 

 

💡  풀이 방식

• LIS (DP)

 

LIS 배열을 만든다.

이 때 String 배열을 숫자의 수만큼 만들고, 최장 길이 수열이 만들어졌을 때 수열 정보를 업데이트한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] A, dp;
    static String[] str;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        A = new int[N];         // 숫자들 배열
        dp = new int[N];        // 각 숫자의 수열의 길이 배열
        str = new String[N];    // 각 숫자의 수열
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
            str[i] = String.valueOf(A[i]);
        }
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < i ; j++) {
                // 현재 숫자보다 왼쪽에 있고, 현재보다 더 긴 수열이 된다면
                if(A[j] < A[i] && (dp[j] + 1 > dp[i])) {
                    dp[i] = dp[j] + 1;
                    str[i] = str[j] + " " + A[i];   // ⭐ i번째 수열 정보 업데이트
                }
            }
        }
        
        int max = 0;    // 최장 길이
        int idx = 0;
        
        for(int i = 0 ; i < N ; i++) {
            if(max < dp[i]) {
                max = dp[i];    // 최장 길이 갱신
                idx = i;        // 최장 길이에서의 인덱스
            }
        }
        
        System.out.println(max);
        System.out.println(str[idx]);
    }
}
 

 

 

 

➕ 다른 풀이 방식

LIS 수열을 출력할 때, DP를 역순으로 순회한 값을 스택에 저장한 풀이! 이게 더 깔끔한 듯✅

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

---

💦 어려웠던 점

- LIS 배열을 어떻게 저장하지?의 문제

 

 

🧐 새로 알게 된 내용

- 스택을 활용한 풀이!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 14002번 : 가장 긴 증가하는 부분 수열 4 - JAVA [자바]