[Java] 백준 14002번: 가장 긴 증가하는 부분 수열 4

[문제 바로 가기] - 가장 긴 증가하는 부분 수열 4

📌 유형 : dp

최장 증가 부분 수열(Longest Increasing Subsequence)로 풀이하는 문제로 원소가 N개인 배열의 부분 수열 중, 각 원소가 이전 원소보다 큰 최대 부분 수열을 구하는 것이다.

6
10 20 10 30 20 50

위의 예제에서는 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]이 된다.

💡 아이디어

dp 배열을 사용해서 풀이할 수 있고, 가장 긴 증가하는 부분 수열의 길이도 구해야 하므로 길이를 저장할 lis 변수를 선언한다.

	dp[0] = 1;
	int lis = 1;
		
	for (int i = 1; i < N; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (nums[i] > nums[j]) {
				dp[i] = Math.max(dp[i], dp[j] + 1);
				lis = Math.max(lis, dp[i]);
			}
		}
	}

dp[i]는 i번째 인덱스에서 끝나는 최장 증가 수열의 길이다.
i를 기준으로 0부터 i-1까지 nums[i] > nums[j]일 경우 증가 수열로 판단하고 dp[i]와 비교한다.

---

풀이

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

/**
 * 백준 14002번 가장 긴 증가하는 부분 수열 4 
 * - LIS
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		
		int[] nums = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp = new int[N];
		dp[0] = 1;
		int lis = 1;
		
		for (int i = 1; i < N; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
					lis = Math.max(lis, dp[i]);
				}
			}
		}
		
		sb.append(lis + "\n");
		
		Stack<Integer> stack = new Stack<>();
		for (int i = N - 1; i >= 0; i--) {
			if (dp[i] == lis) {
				stack.push(nums[i]);
				lis--;
			}
		}
		
		while (!stack.isEmpty()) {
			sb.append(stack.pop() + " ");
		}
		
		System.out.println(sb.toString());
	}
}