[백준_11055번] 가장 큰 증가 부분 수열

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

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

[문제]

 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

 

[입력 조건]

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

[코드]

import java.util.*;

public class BaekJoon_11055 {
	static int n;
	static int[] a,dp;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		a=new int[n];
		dp=new int[n]; // 각 원소의 가장 큰 증가 부분 수열의 합
		
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		
		for(int i=0;i<n;i++) {
			dp[i]=a[i]; // 수열의 시작은 자기 자신이기 때문에 자기 자신의 값으로 초기화
			// 자신보다 왼쪽에 있는 값 탐색
			for(int j=0;j<i;j++) {
				// 자신보다 값이 작다면 dp값 갱신
				if(a[i]>a[j])
					/*
					 * 자신의 증가 부분 수열의 합과
					 * 원소 j의 증가 부분 수열의 합에 자기 자신의 배열 값을 더한 값 중
					 * 큰 값으로 갱신한다.
					 */
					dp[i]=Math.max(dp[i],dp[j]+a[i]);
			}
		}
		
		// 수열의 합이 가장 큰 값 찾기
		int max=-1;
		for(int i=0;i<n;i++)
			max=Math.max(max, dp[i]);
		
		System.out.println(max);
	}

}

 

[고찰]

 이번 문제는 예전에 풀었던 백준 11053번 가장 긴 증가하는 부분수열 문제와 구하는 값만 다른 똑같은 문제였다. 11053번은 수열의 길이를 구하는 반면에 이번 문제는 수열의 합을 구하는 문제였다. 2중 for문을 사용하여 모든 원소를 탐색하는 방법으로 해결하는 것이 더 간단했다. 

 2중 for문을 사용하여 현재 배열의 인덱스보다 배열 인덱스들을 탐색하는데, 이때 현재 배열(i) 값 보다 작은 배열(j) 값을 찾았으면 현재의 증가하는 부분 수열의 합 or j 번째 까지의 증가하는 부분 수열의 합 + i번째 배열 값 중 큰 값으로 dp를 갱신하면 된다.