백준 14002번 가장 긴 증가하는 부분 수열 4 Java (☆공부 269일차)

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

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

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

 

 

 

 

---

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

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	32433	12747	9654	39.223%

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ A_i ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

제한

 

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/250

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

4달 전에 푼 문제

 

StringBuilder()로 출력하는 것만 바꾸고 그대로 풀었다

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
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));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<Integer>();
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        dp = new int[n];
        
        StringTokenizer 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]);
        }
        
        sb.append(max).append("\n");
 
        int idx = max;
        for(int i = n-1; i >= 0; i--) {
            if(dp[i] == idx) {
                stack.push(arr[i]);
                idx--;
            }
        }
        
        for(int i = 0; i < max; i++) {
            sb.append(stack.pop()+" ");
        }
        
        System.out.println(sb);
        br.close();
    }
    
    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];
    }
}

 

 

 

---