[BOJ - JAVA] 11055 - 가장 큰 증가 부분 수열

# 주소

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

11055번: 가장 큰 증가 부분 수열

 

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        for(int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        dp[0] = arr[0];
        for(int i = 1; i <= n; i++) {
            dp[i] = arr[i];
            for(int j = 0; j < i; j++) {
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[j] + arr[i], dp[i]);
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i <= n; i++) {
            if(dp[i] > max){
                max = dp[i];
            }
        }
        System.out.println(max);
    }
}

싸피의 CT에 자주 나오는 문제로 유명한 LIS 문제입니다.

DP를 이용하여 풀어야 하는 문제이고 백트래킹을 이용하여 풀 수는 있지만 메모리를 상당히 잡아먹기 때문에 

비효율적인 부분이 있습니다. 

코드를 보시면 아시겠지만 딱히 어려운 부분은 없습니다. 

다만, 이중 for문에서 dp[i]값을 dp[i]와 dp[j] + arr[i] 중 큰 값을 저장합니다. 

만약 예제에서 1 2 10 4 6이 주어졌을 때

	1	2	10	4	6
arr[i]	1	2	10	4	6
dp[i]	1	3	14	7	13

 

이런 형태의 표가 그려지게 됩니다. 

dp[i]의 값들은 arr[i]가 오름차순일 때 값이 증가하는 성향이 드러나지만

if(arr[i] > arr[j])일 때 Math.max값을 구하는 것이기 때문에 제 아무리 10일 때 dp[i]의 값이 가장 크더라도 

i = 3일 때(arr[i] = 4일 때) arr[i] = 4 > arr[j] = 1 or 2 이므로 (arr[j] = 10 은 arr[i]보다 크므로 사용x)

dp[3]에 보관 되는 값은 7이 됩니다. 

그리고 나서 dp[i]의 최종 값을 출력하면 그것이 정답이 되겠습니다. 감사합니다.