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

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

이 문제는 이 링크의 문제를 읽고 이해하면 쉽게 풀린다.

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

위의 링크의 문제를 이해했으면 이제 수열의 정보만 출력하는 것만 추가하면 된다.

나는 쉽게 String 배열을 숫자의 수만큼 만들어서 가장 긴 수열이 만들어졌을 때 수열의 정보를 업데이트 하고 출력하는 것만 추가하였다.

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;

int N = Integer.parseInt(br.readLine());

// 숫자들 배열
int[] arr = new int[N];
// 각 숫자의 수열의 길이 배열
int[] dp = new int[N];
// 각 숫자의 수열
String[] str = new String[N];

st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
}

// 숫자 배열을 돌면서 수열의 길이를 구한다.
for (int i = 0; i < N; i++) {
	// 먼저 모든 수열은 초기에 자기 자신만 수열로 가지기 때문에
    // 길이는 1, 수열 정보 배열은 자기 자신의 수로 초기화 한다.
    dp[i] = 1;
    str[i] = String.valueOf(arr[i]);
    // arr[i] 왼쪽에 있는 수(arr[j])들을 보면서 arr[i] 보다 작은 수가 있는지 확인
    for (int j = 0; j < i; j++) {
    	// 나보다 작은 수가 있다 &&
        // 이 작은 수 다음으로 내가 와서 수열을 만들었을 때
        // 이 수열이 현재 내 수열보다 더 긴 수열이 되는지 본다.
        // (내가 다음으로 와서 만든 수열의 길이) > (현재 나의 수열 길이)
        // 내가 다음으로 와서 만든 수열의 길이 = 이 작은수의 수열의 길이 + 1 = dp[j] + 1
        // 현재 나의 수열 길이 = dp[i]
        // -> dp[j] + 1 > dp[i]
        if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
        	// 더 길어지면 나의 수열의 길이(dp[i]) 수정
            dp[i] = dp[j] + 1;
            // i 번째 수열의 정보는 j번째의 수열에 i번째 수를 넣은 수열로 수정
            str[i] = str[j] + " " + arr[i];
		}
	}
}

// 만들어진 수열의 길이들 중 가장 긴 길이를 찾는다.
int max = 0;
int index = 0;
for (int i = 0; i < N; i++) {
	if (max < dp[i]) {
		max = dp[i];
		index = i;
	}
}

bw.write(max + "\n");
bw.write(str[index] + "\n");

bw.flush();
bw.close();
br.close();