BOJ 11053: 가장 긴 증가하는 부분 수열 - 자바(java)

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

<접근 방법>

dp를 이용하여 접근해보았다. 문제 예시를 이용하여 확인해보자.
먼저, dp 배열을 만들어보자. dp 배열에는 0번째부터 i번째까지의 수열에서의 가장 긴 증가하는 부분 수열 길이를 저장한다.
 
처음에는 dp 배열의 모든 원소값을 1로 만들어준다. 왜냐하면, 아무리 못해도 1개의 부분 수열이 답이 될 수 있기 때문이다.

최초 생성했을 때의 모습

이제, 규칙을 찾아보도록 하자. 먼저 i = 0은 무조건 1이 된다. 왜냐하면 배열 [10]에는 1개의 원소밖에 없기 때문이다.
 

i = 1일 때, 모습

i = 1일 때를 살펴보자. 0부터 시작해서 arr[1] = 20 보다 작은 값이 무엇이 있는지 확인한다. 여기서는 arr[0] 밖에 없고, 10 < 20 이므로, [10, 20] 이 가장 긴 부분 수열이 된다. 따라서 dp[i] = 2 를 저장한다.
 

i = 2일 때, 모습

i = 2일 때를 살펴보자. 0부터 시작해서 arr[2] = 10 보다 작은 값이 무엇이 있는지 확인한다. 여기서는 2보다 작은 모든 i에 대해서 큰 arr[i]가 존재하지 않는다. 따라서 dp[i] = 1을 유지한다.
 

i = 3일 때, 모습은 어떻게 변경될까??

i = 3일 때를 살펴보자. 0부터 시작해서 arr[3] = 30 보다 작은 값이 무엇이 있는지 확인한다. 여기서는 모든 arr[i]가 30보다 작다. 그렇다면 여기서 가장 긴 부분 수열은 어떻게 찾아야 할까?
 
방법은 0부터 i까지 다시 각각 확인해 보는 것이다. 먼저, i = 0부터 확인해 보자.

1. i = 0 일 때, (dp[0] + 1 = 2) > (dp[3] = 1) 이므로, dp[3] = 2로 변경한다. (즉, [10, 30]일 때이다.)
2. i = 1 일 때, (dp[1] + 1 = 3) > (dp[3] = 2) 이므로, dp[3] = 3으로 변경한다. (즉, [10, 20, 30]일 때이다.)
3. i = 2 일 때, (dp[2] + 1 = 2) < (dp[3] = 3) 이므로, dp[3]은 그대로 유지한다. (즉, [10, 30]일 때이다.)

i = 3일 때, 최종 모습. dp[3] = 3으로 변경된 것을 알 수 있다.

따라서, dp[3]은 3으로 변경된다는 것을 알 수 있다.
 

i = 4일 때, 모습

 
i = 4일 때를 살펴보자. 0부터 시작해서 arr[4] = 20 보다 작은 값이 무엇이 있는지 확인한다. 여기서는 arr[0] = 10, arr[2] = 10이 존재하고, 모든 dp[i] = 1이므로 dp[4] = 2로 변경된다.
 

i = 5일 때, 모습 i를 모두 확인했으므로 획인을 종료한다.

 
 
여기서 dp 배열에서 가장 큰 값이 정답이 된다. 왜 dp 배열의 맨 끝 값(위의 예시에서는 dp[5] = 4)이 정답이 아닌 것일까?
아래의 예시를 살펴보자.

arr = [10, 20, 30, 40, 10, 20] 에서의 계산 결과

 
arr = [10, 20, 30, 40, 10, 20] 에서의 계산 결과이다. 여기서는 길이 4가 정답이되어야 한다. 그러나 dp 배열의 맨 마지막 값인 dp[5] = 2 는 정답이 아니다. 따라서, dp 배열의 최댓값이 정답이 된다는 것을 알 수 있다.
 
따라서, 최종 dp 판정 방법은 아래의 식으로 만들 수 있다.

for i 0 -> n:
    for j 0 -> i - 1:
        dp[j] = max(dp[i], dp[j] + 1);

 

<소스 코드>

위의 접근법을 이용한 전체 소스 코드 구현 결과이다.

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] dp = new int[n];
        int res = 0;
        
        Arrays.fill(dp, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            res = Math.max(dp[i], res);
        }

        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
        br.close();
    }
}