[백준] 11055 가장 큰 증가하는 부분 수열 (자바) : DP [실버2]

✔️ 문제 설명 (펼치기)

 

문제

수열 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)

 

출력

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

 

예제 입력 1 

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1 

113

 

✔️ 문제 풀이  + 코드 구현

저번 포스팅에서 LIS 알고리즘에 대해서 정리해보았다. LIS 알고리즘에 대해서 어느정도 이해가 되었다면 이 문제도 쉽게 풀 수 있다.

[알고리즘] LIS : Longest Increasing Subsequnce 알고리즘 - DP 활용(최장 증가 부분 수열)

 

 

우선 증가하는 부분 수열 중에서 합이 가장 큰 것을 찾아야 된다.

즉, 저번 문제 처럼 가장 긴 수열이 아니라 합이 가장 '큰' 수열을 찾는것이 관건이다. 

문제의 예시로 생각해보면 만들 수 있는 증가하는 부분 수열은 {1, 100}, {1, 2, 50, 60} , {1, 2, 3, 5, 6, 7, 8} 이있다. 

{1, 100} 의 경우에는 합이 101 / {1, 2, 50, 60} 의 경우에는 합이 113 / {1, 2, 3, 5, 6, 7, 8} 의 경우에는 합이 32 이다. 

이때 합이 가장 큰 수열은  {1, 2, 50, 60} 이 되는 것이다. 

 

2024.08.28 - [Coding Test/백준 알고리즘 풀이] - [알고리즘 문제 풀이] 백준 11053번 가장 긴 증가하는 부분 수열 (자바) : DP [실버 2]

에서 소개한 11722번의 경우에는 dp 를 LIS 값 , 즉 그 위치에서의 최대 부분 수열의 길이로 설정하였다. 

 

하지만, 이번 문제의 경우에서는 '합'에 집중해야 하기 때문에, dp 값을 그 위치에서의 수열 중 가장 큰 합으로 설정하면 된다. 

 

알고리즘은 아래와 같다. 

1. 값을 입력받는 동시에 자기 자신의 값(부분 수열의 합)으로 dp 초기화
   arr : 전체 수열을 담는 배열 
   dp : 자기 자신을 포함한 부분 수열까지의 합 중 최대값

	int[] arr = new int[n];
        int[] dp = new int[n]; //dp는 자기 자신을 포함한 수열까지의 합
        for(int i = 0 ; i < n ; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = dp[i] = num;
        }

   

       2.  이중 for 문으로 dp[i] 후보들 중 최대값 고르기
             max : 문제에서 구하고자 하는 부분 수열 합의 최대값

	for(int i = 1; i<n; i++){
            for(int j = 0; j<i; j++){
                if(arr[j] < arr[i]){
                    dp[i] = Math.max(dp[i], dp[j]+arr[i]);
                }
            }
            max = Math.max(max, dp[i]);
        }

 

[전체 코드]

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n];
        int[] dp = new int[n]; //dp는 자기 자신을 포함한 수열까지의 합
        for(int i = 0 ; i < n ; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = dp[i] = num;
        }

        int max = dp[0];

        for(int i = 1; i<n; i++){
            for(int j = 0; j<i; j++){
                if(arr[j] < arr[i]){
                    dp[i] = Math.max(dp[i], dp[j]+arr[i]);
                }
            }
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}