공부 129일차: 백준 14002번 가장 긴 증가하는 부분 수열 4 자바 java

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

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

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

 

 

 

 

---

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

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/249

공부 128일차: 백준 11053번 가장 긴 증가하는 부분 수열 자바 java

LIS를 구하는 건 이 게시글을 참고하면 된다

 

다른 점은 그 수열에 해당하는 수까지 반환해야 한다는 점인데,

앞서 구한 수열의 최대 크기부터 dp[i]를 거꾸로 돌려서 값이 일치할 때마다 출력해주면 될 것 같다

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] arr;
    static int[] dp;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        Stack<Integer> stack = new Stack<Integer>();
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        dp = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            LIS(i);
        }
        
        int max = dp[0];
        for(int i = 1; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        
        System.out.println(max);
 
        int sequence = max;
        for(int i = n-1; i >= 0; i--) {    // 앞서 구한 수열의 최대 크기서부터 1이 될 때까지 
            if(dp[i] == sequence) {    // 수열 크기 값이 같으면
                stack.push(arr[i]);    // 스택에 저장
                sequence--;    // 크기가 같은 수열이 2개 이상 출력되지 않도록 바로 -1을 해준다
            }
        }
        
        // 수열의 개수 = 앞서 구한 수열의 최대크기
        for(int i = 0; i < max; i++) {
            // 수열의 최대 크기부터 거꾸로 넣었으므로 스택으로 꺼내는 것이 적절하다
            System.out.print(stack.pop()+" ");
        }
    }
    
    public static int LIS(int n) {
        if(dp[n] == 0) {
            dp[n] = 1;
            
            for(int i = n-1; i >= 0; i--) {
                if(arr[i] < arr[n]) {
                    dp[n] = Math.max(dp[n], LIS(i)+1);                    
                }
            }
        }
        return dp[n];
    }
 
}
 

 

오랜만에 스택 사용!

적절하게 사용할 때마다 지금까지 한 게 헛되진 않은 것 같다는 생각이 든다

 

 

---