백준 14002 Java

문제

---

예제와 같이 만약 10, 20, 10, 30, 20, 50 이라는 수열이 있다면

증가하는 2개의 부분 수열을 볼 수 있다.

먼저 최대 길이를 갖는 10, 20, 30, 50 과 나머지 10, 20

index	1	2	3	4	5	6
수열	10	20	10	30	20	50
dp	1	2	1	3	2	4

---

Code

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class P14002 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine()); // 수열 길이
		int[] arr = new int[N + 1]; // 수열
		int[] dp = new int[N + 1];  // 부분 증가 수열의 인덱스 
		
		int len = 1; // 부분 증가 수열 길이
		dp[1] = 1;
		
		/*
		ex)
		arr(수열) : 10 20 10 30 20 50  --> 2개의 증가 부분 수열(10, 20, 30, 50 / 10, 20) 존제
		dp : 	   1  2  1  3  2  4	  --> (1, 2, 3, 4 / 1, 2)	
		*/
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 2; i <= N; i++) {
			dp[i] = 1;
			for(int j = 1; j < i; j++) {
				if(arr[i] > arr[j] && dp[i] <= dp[j]) {
					dp[i] = dp[j] + 1;
				}
			}
			len = Math.max(len, dp[i]);
		}
		
		
		int val = len;
		Stack<Integer> stack = new Stack<Integer>();
		for(int i = N; i >= 1; i--) {
			if(val == dp[i]) {
				stack.push(arr[i]);
				val--;
			}
		}
		bw.write(len + "\n");
		while(!stack.isEmpty()) {
			bw.write(stack.pop() + " ");
		}
		bw.flush();
		bw.close();
		br.close();
	}

}

---

참고 : https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-14002%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-4-Java-%EC%9E%90%EB%B0%94