알고리즘 풀이 - 백준 11055(가장 큰 증가 부분 수열, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
LIS 관련 포스팅은 여기를 참조
관련 문제인 11053번(가장 긴 증가하는 부분 수열) 포스팅은 여기를 참조
관련 문제인 14002번(가장 긴 증가하는 부분 수열 4) 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 LIS를 구하고 그 배열의 합을 구하는 문제이다.

 

 

 

2. 풀이

 

이 문제는 상단의 관련글에서 표기한 LIS 포스팅을 보는 것이 더 낫다.
간단히 이야기하여 순차적으로 저장된 데이터가 있는 배열의 부분 배열 중 증가하면서 가장 긴 부분 배열을 구하는 문제이다.

 

이 문제는 기본적으로 DP로 풀 수 있고, 그 보다 더 개선된 시간복잡도를 갖는 방식으로 풀어내는 것도 가능하다. 해당 내용 또한 상단의 LIS 포스팅에 있으니 참고하자.

 

간단히 문제의 정의, 기저 상태, 점화식을 알아보자.

정의 : 길이 N의 배열에서 LIS의 값의 합 중 최대값 구하기

길이 N이라는 값 자체가 State이므로 배열의 길이에 따른 결과값만 저장하는 배열을 별도로 생성한다. DP의 결과를 저장할 배열을 sum[]라고 부르자. 그 크기는 기존 배열과 같게 생성하면 될 것이다.

 

그렇다면, 기저 상태는 어떻게 되나? 배열의 길이가 1일 때이다. 즉 N=1, index로는 0일 때, 그 자체로만 LIS가 되므로 그 상태 지정을 할 수 있다.
기저 상태 : sum[0] = arr[0]

 

제일 중요한 점화식을 알아보자. LIS의 특성에 따라 점화식은 다음과 같이 지정할 수 있다.
점화식 : sum[i] = MAX(sum[i], sum[j] + arr[i]) (단, j < i and arr[j] < arr[i])

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[] arr;
    static int[] sum;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[1000];
        sum = new int[1000];
        
        String line[] = br.readLine().split(" ");
        
        for(int i=0; i < n; i++){
            arr[i] = Integer.parseInt(line[i]);
        }
        
        // 기저 상태
        sum[0] = arr[0];
        
        int max = sum[0];
        for(int i=1; i < n; i++){
            sum[i] = arr[i];
            
            for(int j=i-1; j >= 0; j--){
                if(arr[i] > arr[j]){
                    sum[i] = Math.max(sum[i], sum[j] + arr[i]);
                }
            }
            max = Math.max(max, sum[i]);
        }
        
        bw.write(String.valueOf(max));
        br.close();
        bw.flush();
    }
}

 

2) Top-Down 방식

import java.io.*;
public class Main{
    static int[] arr;
    static int[] sum;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[1000];
        sum = new int[1000];
        
        String line[] = br.readLine().split(" ");
        
        for(int i=0; i < n; i++){
            arr[i] = Integer.parseInt(line[i]);
        }
        topDown(n-1);
        int result = 0;
        for(int i=0; i < n; i++){
            result = Math.max(result, sum[i]);
        }
        
        bw.write(String.valueOf(result));
        br.close();
        bw.flush();
    }
    
    // Top-Down 방식으로 해결하는 DP
    public static int topDown(int n){
        if(n == 0) return sum[n] = arr[n]; // 기저상태 또는 이미 이전의 값이 있는 경우
        if(sum[n] > 0) return sum[n];
        
        sum[n] = arr[n]; // 우선 원 배열 값으로 초기화
        for(int i=n-1; i >= 0; i--){
            if(arr[i] < arr[n]){
                sum[n] = Math.max(sum[n], topDown(i) + arr[n]);
            // 이 부분이 중요!
            // 만약 현재 값이 가장 작다면 더 이상 이전으로 가지 않아서 TopDown이 수행되지 않을 수 있다.
            } else {
                topDown(i);
            }
        }
        return sum[n];
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.