백준 11722번: 가장 긴 감소하는 부분 수열

문제

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

11722번: 가장 긴 감소하는 부분 수열

---

풀이

14002번 문제와 반대로 LDS(Longest Decreasing Subsequence)를, 즉 어떤 수열이 주어졌을 때 가장 긴 감소하는 부분 수열을 구하는 문제입니다.

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

---

코드

자바

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

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

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

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

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

public class Main {

    static int[] arr, dp;

    public static int LDS(int idx) {
        if (dp[idx] == 0) {
            dp[idx] = 1;
            for (int i = idx + 1; i < dp.length; i++) {
                if (arr[i] < arr[idx]) {
                    dp[idx] = Math.max(dp[idx], LDS(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, LDS(i));
        }
        System.out.println(max);
    }
}

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를 구한 뒤에 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#define math_max(a, b) a > b ? a : b
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 = n - 1; i >= 0; i--) {
		for (int j = n - 1; 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", max);
}

---

결론

dp를 이용하여 LIS(Longest Increasing Subsequence)와 반대되는 LDS를 구현하여 문제를 해결하였습니다. LIS 문제와 dp 배열이 갖는 의미가 조금 달랐고 앞으로도 다른 문제를 풀 때 dp 배열이 갖는 의미가 계속 달라질 텐데 도움이 됐으면 좋겠습니다.