Calm Dawn Studio

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

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

public class Main {

	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[] A = new int[N]; // 수열 A
		int[] dp = new int[N]; // 각 수열의 증가부분 최대 길이

		int result = 0;
		String[] route = new String[N];
		int locate = 0;

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			String number = st.nextToken();
			A[i] = Integer.parseInt(number);
			route[i] = number;

		}

		for (int j = 0; j < N; j++) {
			dp[j] = 1;
			for (int k = 0; k < j; k++) {
				if (A[j] > A[k] && dp[k] >= dp[j]) { // 현재 수와 이전까지의 수들 크기비교
					dp[j] = dp[k] + 1; // 각각의 최대길이 비교해서 가장큰값을 저장
					route[j] = route[k] + " " + A[j];
				}
			}

		}

		for (int i = 0; i < N; i++) {
			if (result < dp[i]) {
				result = dp[i];
				locate = i;
			}

		}

		bw.write(String.valueOf(result));
		bw.newLine();
		bw.write(route[locate]);
		bw.flush();
		bw.close();
	}

}

정답을 맞춘 풀이방법

1 . 기존에 풀었던 11053번 문제에 수열의 최대길이의 경로까지 함게 출력하는 문제로 경로를 저장할 String[] route배열을 추가함

2.  최대경로값을 가진 주소 locate를 구한 후  해당하는 경로를 가진 route배열 값을 출력함