[백준] 11053번: 가장 긴 증가하는 부분 수열 (java)

문제 링크

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

---

오랜만에 DP 문제를 들고 왔습니다!

이 문제는 그 이름도 유명한 가장 긴(최장) 증가 부분 수열 (LIS: Longest Increasing Subsequence) 입니다.

이 문제는 시리즈(1번부터 5번)가 있으며, 나무위키에 등재되어 있을 정도로 잘 알려져 있습니다.

문제를 차근차근 살펴보며 풀이해봅시다!

풀이

DP를 이중선형시간(\(O(N^2)\))으로 메모라이즈하며 LIS의 길이를 구하면 됩니다.

이 문제에서는 \(O(N^2)\) 에 해결할 수 있는 n값의 범위( \( 0 \leq N \leq 1000 \) )를 조건으로 제시하고 있습니다.

2번부터는 선형탐색보다 더 빠른 알고리즘으로 접근해야되지만, 선형탐색으로 시간이 충분(\(1000*1000\))하기 때문에 선형탐색으로 진행해보도록 하겠습니다.

저는 아래 2개의 배열을 이용해서 알고리즘을 진행했습니다.

• inp : 초기에 주어진 입력 배열
• dp : 값을 처음부터 비교해봤을 때 가장 긴 수열의 길이를 저장하는 배열

초기상태의 dp[0] 값은 1이며, 앞으로 저장될 dp의 값들은 모두 1이 베이스가 됩니다.

왜냐하면 자기 자신만 존재하는 수열(예: {10}, {20})이 수열의 부분집합의 가장 작은 길이가 될 것이기 때문입니다.

dp[1]부터는 차례로 뒤에 있는 수들과 나의 수를 비교해보며 값이 자신보다 작으면서 + 길이가 가장 긴 값을 찾아냅니다.

그 값 중에 제일 긴 값이 이 문제의 답이 될 것입니다.

DP 점화식은 다음과 같습니다.

\[ dp[i] = max(dp[i], \; dp[j] + 1) \quad \text{if } \; inp[j] \le inp[i] \; (0 \le j <  i) \]

풀이코드

import java.io.*;
import java.util.*;

class Main {

    static int[] dp;
    private static void solve(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[] inp = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt).toArray();
        dp = new int[n];
        dp[0] = 1;
        int maxCnt = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (inp[j] < inp[i] && dp[i] < dp[j] + 1) {
                    dp[i]++;
                }
            }
            maxCnt = Math.max(maxCnt, dp[i]);
        }
        res.append(maxCnt);
    }

    private static StringBuilder res;
    public static void main(String args[]) throws Exception {
        if (args.length > 1) fileInputOutput(args[0], args[1]);
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            res = new StringBuilder();
            solve(br);
            bw.write(res.toString());
        }
    }

    private static void fileInputOutput(String inputPath, String outputPath) throws IOException {
        System.setIn(new FileInputStream(inputPath));
        System.setOut(
            new PrintStream(
                new BufferedOutputStream(
                    new FileOutputStream(outputPath)
                )));
    }
}

 

배운점

• LIS 알고리즘을 배울 수 있었습니다.
• bottom-up DP를 복습할 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!