[백준,BOJ 11055] 가장 큰 증가 부분 수열( JAVA 구현)

-내 생각

  이 문제는 이전에 풀었던 가장 긴 증가 부분 수열인 LIS 문제와 동일한 문제였다. 차이점이라 한다면, DP 배열에 저장되는 값이 부분 수열의 길이가 아닌, 부분 수열의 합이 된다는 점이다. 그렇기 때문에 기본이 되는 알고리즘은 LIS를 구하는 문제와 동일하다. 

 

-해법

  이런 식의 부분 증가수열은 기준점을 잡은 후 기준점 이전까지의 수들과 비교하여 자신이 큰 경우만 DP 배열을 갱신해주면 된다. 예를들어 2를 기준으로 잡았을 때, 2의 이전 숫자들인 과 100을 2와 비교해서 2가 큰 경우, 비교했던 숫자가 가지고 있는 dp값 + 기준이 되는 자신의 값으로 갱신해주면 되는데, 이때 주의해야 할 점은 100은 2보다 크기 때문에 자신의 dp배열을 갱신해주어야 한다. 이 경우에는 이전에 선택한 값이 없기 때문에 자기 자신의 값이 dp배열에 경신된다. 

 

  위와 같은 흐름으로 dp 배열을 갱신해주기 위해서는 Math.max메소드를 활용하여 기준으로 잡혔을 때, 자기 자신의 값을 미리 dp배열에 저장한 후, 비교 시 조건에 걸린다면, 자신의 값과 더해진 값을 비교해 더 큰 값을 dp배열에 저장하면 된다. 예를 들어 기준이 100이라 할 때, dp [2] = 100이 되고, 1을 100과 비교하면 조건에 걸리기 때문에 1에 이미 저장되어 있던 1과 자신의 값을 더해 기존에 있던 100과 비교해 큰 값을 넣게 된다. (Math.max( 1+100, 100))

 

import java.util.*;
import java.math.*;
public class Main {
	
	static int dp[],cost[] ;
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		//dp 배열과 비용배열 선언
		dp = new int[n+1];
		cost = new int[n+1];
        
		for(int i=1;i<=n;i++) {
			cost[i] = sc.nextInt();
		}
		
		dp[1] = cost[1]; // dp[1]은 항상 cost[1]로 초기화 된다. 이전에 더해진 값이 없기 때문
		
		for(int i=2;i<=n;i++) { //두 번째 숫자를 기준으로 n까지 반복
			dp[i] = cost[i]; // 우선 자신의 값을 dp에 저장해 둔다.
			for(int j=1;j<i;j++) { // 첫 번째 부터 i이전 까지 비교를 위한 반복
				if(cost[i]>cost[j]) { // 기준값이 더 큰 경우
					dp[i] = Math.max(dp[j]+cost[i],dp[i]); // 증가 수열이므로 dp값 갱신
				}
			}
		}
		int max = Integer.MIN_VALUE;
		for(int i=1;i<=n;i++) {
			if(dp[i]>max) {
				max = dp[i];
			}
		}
		System.out.println(max);
	}
	
}