[Java] BOJ/백준 11053번 가장 긴 증가하는 부분 수열

[문제]

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

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

 

[풀이]

📌 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘

원소가 n개인 배열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다.

 

일반적으로 LIS의 길이를 구하는 간편한 방법은 DP를 이용하는 것이다.

+ 이분탐색을 이용해 구하는 방법도 있다.

---

문제에 나온 예제 (10, 20, 10, 30, 20, 50)를 순차적으로 seq 배열에 담는다.

메모이제이션 기법을 이용해 LIS 길이를 담을 dp 배열을 선언한다.

seq[0]보다 이전 값은 없기 때문에 LIS는 부분수열 {10}이 되어 dp[0] = 1 이다.

seq[1] 값인 20은 seq[0] = 10 보다 크기 때문에 부분수열 {10, 20}이 되고, 길이는 2이기 때문에 dp[1] = 2 이다.

seq[2] 값인 10은 이전 값들 중 10보다 작은 게 없어 부분수열 {10}이 되어 dp[2] = 1 이다.

이런 식으로 dp 배열값을 채워나가면 위와 같은 결과가 나온다.

 

DP는 Top-Down(재귀) 방식이 있고, Bottom-Up(반복문) 방식이 있는데 나는 Bottom-Up 방식으로 풀어보았다.

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

이중 반복문으로 0부터 N - 1까지 기준 원소가 각 원소보다 클 경우, (기준 원소의 LIS 길이 vs 해당 원소의 LIS 길이 + 1) 중 더 큰 값을 기준 원소의 LIS 길이로 저장하는 것이다.

 

예를 들어 위 예제에서 i = 3일 때 우선 dp[3] = 1로 초기화되고, j는 0부터 2까지 순회한다.

1️⃣ j = 0일 때

seq[0] = 10은 기준 값 30보다 작기 때문에 dp[3] = 1 값과 dp[0] = 1 + 1 = 2 를 비교해 더 큰 값인 2가 저장된다.

 

2️⃣ j = 1일 때

seq[1] = 20은 기준 값 30보다 작기 때문에 dp[3] = 2 값과 dp[1] = 2 + 1 = 3 를 비교해 더 큰 값인 3이 저장된다.

 

3️⃣ j = 2일 때

seq[2] = 10은 기준 값 30보다 작아 dp[3] = 3 값과 dp[2] = 1 + 1 = 2 를 비교하지만 기존 값이 더 크기 때문에 그대로 3으로 유지된다.

 

dp 값을 다 구하면 dp 배열에서 가장 큰 값을 찾아 출력한다.

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int seq[] = new int[N];
        for (int i = 0; i < N; i++) seq[i] = Integer.parseInt(st.nextToken());

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

        int max = -1;
        for(int i = 0; i < N; i++) {
            max = dp[i] > max ? dp[i] : max;
        }
        System.out.println(max);
    }
}