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

문제

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

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

 

---

풀이

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

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 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];
        dp = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, LIS(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 = 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", max);
}

 

---

결론

LIS를 구현할 수 있는 많은 방법 중 dp를 이용하여 문제를 해결했습니다. 또한 이 문제에서는 길이의 최댓값만 구했지만 좀 더 응용하면 가장 긴 길이의 부분 수열이 어떻게 이루어져 있는지 구할 수 있을 것 같았습니다.