[PS] 백준 11055번 가장 큰 증가 부분 수열 - DP

문제

예제

풀이

가장 긴 증가 부분 수열 문제를 변형한 문제이다.

이전 문제와 다른 것은 dp[탐색위치]에 수열의 길이가 아니라 증가수열의 누적합을 저장하는 것이다.

우선 arr 배열에 입력값을 저장한다. dp[1]은 초기 누적합이므로 arr[1] 그대로를 저장한다.

dp[i] 값을 저장하기 위해 i=2부터 n일 때까지 반복문을 돈다.
우선 현재 위치의 누적합 dp[i]에 값 그대로 arr[i]를 저장한다.

현재위치는 i이고, arr배열을 j=1부터 현재위치 이전(i-1)까지 탐색한다고 할 때,

​

가장 큰 증가수열이여야 하므로

1. 현재 값 arr[i]가 탐색값 arr[j]보다 크다면
2. 이전누적합 + 현재위치값 과 현재누적합 중 큰 것을 dp[i]에 저장한다. (그래야 가장 큰 합의 증가수열 누적합을 저장할 수 있다.)
   • 코드로 표현하면 dp[i] = Math.max(dp[j]+arr[i], dp[i]);이 된다. 이 부분에서 막혀서 구글링해서 잠깐 참고했다.

​

설명만으론 조건 2가 이해가 잘 안될 수 있는데
예를 들어 문제의 예제에서 마지막에 90을 추가했다고 가정해보자.

​

idx	1	2	3	4	5	6	7	8	9	10	11
arr	1	100	2	50	60	3	5	6	7	8	90
dp	1	101	3	53	113	6	11	17	24	32	203

​

반복문의 j로 쭉 탐색한다고 했을 때 90의 dp값은 이렇게 바뀐다.

j=1 : 90 < (1의 누적합 1 + 90)91 -> 91
j=2 : 91 -> 90이 100보다 작으므로 패스
j=3 : 91 < (2의 누적합 3 + 90)93 -> 93
j=4 : 93 < (50의 누적합 53 + 90)143 -> 143
j=5 : 143 < (60의 누적합 113 + 90)203 -> 203
j=6 : 203 > (3의 누적합 6 + 90) -> 203
...
j=10 : 204 > (8의 누적합 32 + 91)93 => 204

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[] arr = new int[n+1];//값
        int[] dp = new int[n+1];//dp[탐색위치]에 증가수열의 누적합 저장

        for(int i=1; i<=n; i++) {
            arr[i] = in.nextInt();
        }

        dp[1] = arr[1]; // 초기 누적합은 값이 1개라 그대로 저장한다.
        int max = arr[1];

        for(int i=2; i<=n; i++) {
            dp[i] = arr[i];
            for(int j=1; j<i; j++) {//1부터 현재위치까지 탐색

                //dp를 arr[1]부터 비교하면서 초기화
                if(arr[i] > arr[j]) { //현재 값이 탐색값보다 크면(증가수열)
                    dp[i] = Math.max(dp[j]+arr[i], dp[i]); // (이전누적합 + 현재위치값)과 현재누적합중 큰 것 저장
                }
            }
            max = Math.max(max,dp[i]); //최대값과 비교
        }

        System.out.println(max);
    }
}