[JAVA] 백준 11055번 【가장 큰 증가 부분 수열】

---

dp 배열을 생성하고 dp[i]에는 i 번째 원소가 형성하고 있는 부분 수열의 합을 넣을 것이다.

 

즉, dp[i] 는 수열의 i번째 원소까지 가장 큰 부분수열의 합을 기록할 것이다.

 

예를 들면 A = [1 2 3 10 5 14] 가 있다고 할때

 

dp = [1 3(1+2) 6(1+2+3) 16(1+2+3+10) 11(1+2+3+5) 30(1+2+3+10+14)] 

     = [1 3 6 11 16 30] 

이 되는 것이다.

 

여기서 중점적으로 봐야할 포인트는, dp[5]를 구할때이다.

 

부분 수열의 경우의 수가 2가지 존재한다.

 

[1 2 3 5 14 ] 즉, 총합이 25가 되는 경우와

[1 2 3 10 14] 즉, 총합이 30이 되는 경우의 수가 존재한다.

 

채우는 방법은, 30보다 작은 원소를 발견하면, 그 원소가 갖고있는 dp값에 자기 자신(30)을 더한 값이

 

30까지의 부분수열의 합이 된다.

 

30보다 작은원소가 갖고있는 dp값에 자기자신(30)을 더한 값이 이미 기록된 부분수열의 합보다 작은 경우는 업데이트 하지 않으면 된다.

 

---

 

dp[5] 을 채워야 하는 상황이라고 생각해보자

 

dp[4] 까지는 이미 해당 원소가 이루고 있는 부분수열 중 가장 큰 총합이 기록되어 있다.

 

 

 

 

 

Array[0] = 1 < Array[5] = 14  조건을 만족한다.

 

또한, dp[5] = 0 < dp[0] + Array[5] = 1+14 만족하므로, dp[5]= dp[0] +Array[5] = 15 으로 업데이트한다.

 

 

 

Array[1] = 2 < Array[5] = 14  조건을 만족한다.

 

또한, dp[5] = 15 < dp[1] + Array[5] = 3+14 =17 만족하므로, dp[5]= dp[1] +Array[5] = 17 으로 업데이트한다.

 

 

 

 

Array[2] = 3 < Array[5] = 14  조건을 만족한다.

 

또한, dp[5] = 17 < dp[2]+ Array[5] = 6+14 =20 만족하므로, dp[5]= dp[2] +Array[5] = 20 으로 업데이트한다.

 

 

 

 

 

Array[3] = 10 < Array[5] = 14  조건을 만족한다.

 

또한, dp[5] = 20 < dp[3] + Array[5] = 16+14 =30 만족하므로, dp[5]= dp[1] +Array[5] = 30 으로 업데이트한다.

 

 

 

 

Array[4] = 5 < Array[5] = 14  만족한다.

 

하지만, dp[5] = 30 >  dp[4] + Array[5] = 11+14 =25 조건을 불만족하므로, 업데이트하지 않고 dp[5] = 30으로 유지한다.

 

결과적으로 가장 큰 부분수열이 기록된다.

 

 

 

---

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.valueOf(br.readLine());
		int[] dp = new int[N + 1];
		int[] array = new int[N + 1];
		String[] input = br.readLine().split(" "); // 수열을 split을 이용하여 공백을 기준으로 나눈 String 배열로 입력 받는다.
		
		
		for (int i = 1; i <= N; i++) {
			array[i] = Integer.valueOf(input[i - 1]); //입력받은 수열이 String이기 때문에, int로 바꾼 후 array 배열을 채운다.
			dp[i]=array[i];
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j < i; j++) {
				if (array[i] > array[j] && dp[j] + array[i] > dp[i]) { 
                //1 ~ i-1 번째 원소들 중 i보다 작은 경우 그리고 현재 dp[i] 보다 dp[j]+array[i]가 큰 경우 업데이트
					dp[i] = dp[j] + array[i]; 
                    
				}

			}
		}
		System.out.println(Arrays.toString(dp));
		Arrays.sort(dp); //dp를 오름차순으로 정렬해줌
		System.out.println(Arrays.toString(dp));
		System.out.println(dp[N]); // 제일 뒤에있는 값이 최댓값일 것

	}
}