백준 14002 가장 긴 증가하는 수열 4
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.
포인트
유명한 LIS 문제이다. 길이만 구하는 것뿐만 아니라 그 부분 수열을 정확하게 구해야한다.
LIS 문제에는 2가지 알고리즘이 있다. 하나는 O(N^2) 시간복잡도를 갖고, 다른 하나는 O(N logN)의 시간 복잡도를 갖는다.
이 문제는 N의 범위가 1000이고 O(N^2)의 풀이로도 1초안에 수행할 수 있으므로 O(N^2)의 풀이로 해결하였다.
import java.io.*;
import java.util.*;
public class LIS_14002 {
static int[] arr, dp;
static int N;
static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
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());
}
dp[0] = 1;
int max = dp[0];
for (int i = 1; i < N; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
max = Math.max(dp[i], max);
}
}
}
int ret = max;
for (int i = N - 1; i >= 0; i--) {
if(max == dp[i]) {
stack.push(arr[i]);
max--;
}
}
while(!stack.isEmpty()) {
sb.append(stack.pop()).append(" ");
}
bw.write(ret + "\n" + sb.toString() + "\n");
bw.flush();
bw.close();
}
}
Stack을 이용해서 역추적할 수 있도록 했다.
Author And Source
이 문제에 관하여(백준 14002 가장 긴 증가하는 수열 4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dls4585/백준-14002-가장-긴-증가하는-수열-4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)