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

문제

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

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

 

---

풀이

14002번 문제를 응용한 문제로 LIS(Longest Increasing Subsequence)를, 즉 어떤 수열이 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 이때 수열이 여러 가지가 될 수 있는 경우에는 아무거나 출력합니다.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

dp 배열은 각 인덱스가 맨 오른쪽인 부분 수열이 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 의미합니다.

LIS 함수에서 dp[idx]가 0이라면 1로 초기화한 뒤에 i를 포함한 for문에서 arr[idx]와 arr[idx보다 앞쪽에 있는 인덱스(i)]를 비교합니다. 만약 arr[i]가 arr[idx]보다 작다면 LIS 함수를 재귀적으로 실행하며 dp[idx] 값을 최신화한 후에 for문이 끝나면 그 값을 반환합니다.

모든 입력이 끝나면 i를 포함한 for문에서 LIS(i)를 1부터 n까지 실행하며 최댓값 max를 구한 뒤에 Stringbuilder sb에 그 값을 추가합니다.

이후에 해당 부분 수열을 출력하기 위해 스택과 while문을 사용하는데 dp[n]이 max값과 다르다면 그다음을 탐색하기 위해 n값을, 같다면 arr[n]을 스택에 삽입한 뒤에 n값과 max값을 1씩 줄여가며 비교합니다.

모든 비교가 끝나고 스택에 모든 값이 들어갔다면 sb에 스택의 모든 값을 문제 조건에 맞게 넣어준 뒤에 sb를 출력합니다.

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

public class Main {

    static int[] arr, dp;

    public static int LIS(int idx) {
        if (dp[idx] == 0) {
            dp[idx] = 1;
            for (int i = idx - 1; i > 0; i--) {
                if (arr[i] < arr[idx]) {
                    dp[idx] = Math.max(dp[idx], LIS(i) + 1);
                }
            }
        }
        return dp[idx];
    }

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

C언어

바텀업 방식을 이용한 코드입니다.

dp 배열은 탑다운 방식의 코드에서의 의미와 동일하며 i를 포함한 for문으로 arr[i] 값을 입력받으며 dp[i]는 1로 초기화합니다.

이후 i와 j를 포함한 이중 for문으로 arr[i]값이 arr[i보다 앞에 있는 인덱스(j)]보다 크고 dp[i]보다 dp[j] + 1이 크다면 그 값을 넣어줍니다.

이후 i를 포함한 for문에서 dp[i] 값을 비교하며 최댓값 max를 구한 뒤에 출력한 후에 탑다운 방식의 코드와 동일하게 해당 부분 수열을 출력하기 위해 스택과 while문을 사용하는데 1부터 n이 아닌 0부터 n - 1번 인덱스를 사용하기 때문에 dp[n]와 max값을 비교하기 전마다 n값을 1씩 줄입니다. dp[n]이 max값 두 값이 같다면 arr[n]을 스택에 삽입한 뒤에 n값과 max값을 1씩 줄여가며 비교합니다.

모든 비교가 끝나고 스택에 모든 값이 들어갔다면 스택의 모든 값을 문제 조건에 맞게 출력합니다.

#include <stdio.h>
#define math_max(a, b) a > b ? a : b
int stack[1001], idx = -1;
void push(int value) {
	stack[++idx] = value;
}
int pop() {
	if (idx < 0) return -1;
	else return stack[idx--];
}
int is_empty() {
	if (idx < 0) return 1;
	else return 0;
}
main() {
	int n;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	int* dp = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		dp[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
		}
	}
	int max = 0;
	for (int i = 0; i < n; i++) {
		max = math_max(max, dp[i]);
	}
	printf("%d\n", max);
	while (max > 0) {
		n--;
		if (max == dp[n]) {
			push(arr[n]);
			max--;
		}
	}
	while (!is_empty()) {
		printf("%d ", pop());
	}
}

 

---

결론

dp로 LIS를 구현하여 문제를 해결했습니다. 이 문제에서는 길이의 최댓값만 구하지 않고 해당 부분 수열이 어떤 값을 포함하고 있는지 또한 구했습니다. 다른 문제에서 수열의 크기 n의 범위가 너무 커서 이러한 방식으로 문제를 풀 수 없었는데 추후에 정리해보도록 하겠습니다.