[Day28]JAVA 백준 가장 큰 증가하는 부분 수열(11055번)

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

 

백준 110055번은 DP(동적 계획법) 을 활용하여 해결 할 수 있다.

---

🌘문제 이해하기

 

• 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
• 첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

---

🌗문제 자세히보기

 

수열의 증가하는 부분 수열 이란??

 

크기가 10인 수열을 예시로 들겠다. 

int[] arr = new int[10]

 

이때 증가하는 부분 수열 라는 것은 아래와 같이 수열에 증가하는 흐름을 가진 부분들을 모아 부분 수열이라고 말한다

1 > 100

1 > 2 > 50 > 60 

1 > 2 > 3 > 5 > 6 > 7 > 8  

 

하지만 기존에 저장되어있는 수열의 순서가 바뀌는 것은 부분수열이라고 할 수 없다.

1 > 50 > 60 > 100 

 

이 수열에서 합이 가장 큰 것을 구하는 방식을 알아보겠다.

1. 수열의 순서대로 숫자 하나를 기준으로 잡흔다.

2. 기준이된 숫자의 이전 순서의 숫자들과 비교한다.

3. 이전보다 숫자가 증가 하는지 감소하는지를 확인하여 부분수열에 포함

 

문제에 따라 부분 수열의 길이 , 부분 수열의 합을 구하라고 하는데 이번에는 부분 수열의 합을 구하는 문제이다.

 

4. 수열크기만큼의 합을 넣을 수 있는 배열을 생성한다.

dp 에는 각 수열의 숫자로 초기화 한다.

int[] dp = new int[n]
dp[i] = arr[i]

맨 처음 1번째의 숫자 1은 비교할 대상이 없으므로 부분 수열의 합이 1이다.

dp[0] = 1 저장 

두 번째의 숫자 100 을 기준으로 잡고 첫번째에 있는 숫자 1과 비교한다.

기준값 : 1 , 비교값 : 100

100 > 1 이므로 증가하는 흐름으로 부분수열에 적합하다.

고로 dp[1] = max(dp[1]  . dp[0]+ arr[1] )  = max(100, 1 +100 ) = 101 

 

세번째 숫자 2를 기준으로 잡고 첫번째 , 두번째에 있는 숫자들과 비교한다.

기준값 : 2 , 비교값 : 1

2 > 1 이므로 증가하여 첫번째 숫자는 부분수열에 적합하다.

dp[2] = max(dp[2] , dp[0]+ arr[1]) = max(2 , 1 +2) = 3

기준값 : 2 , 비교값 : 100

2 < 100 으로 감소하므로 두번째 숫자는 부분수열에 적합하지 않다. 

고로 부분 수열은 dp[2] = 3 저장한다.

 

네번째 숫자 50을 기준으로 첫번째 , 두번째 , 세번째 에 있는 숫자들과 비교한다. 

기준값 50 , 비교값 : 1

50 > 1 증가 , 부분수열 적합

dp[3] = max(dp[3] , dp[2]+ arr[0] ) = max(50, 50+1) = 51

 

기준값 : 50 , 비교값 : 100

50 < 100 감속 , 조건 불만족

 

기준값 : 50 , 비교값 : 2

50 > 2 증가 , 부분수열 적합 

dp[3] = max(dp[3] , dp[2] + arr[2]  = max(51, 3+ 50) = 53

 

이렇게 기준값을 잡고 그 이전의 값들과 비교하면서 부분 수열의 합을 더해주면된다. 

최대합을 유지하지 위해서 max(dp[i] , dp[j] + arr[i])  공식을 사용해 준다. 

 

---

🌕 최종코드 

import java.util.*;
import java.io.*;
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()); //수열의 개수 

        int[] arr = new int[n]; //수열
        int[] dp = new int[n]; //증가하는 수 

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i =0;i<n;i++)
        {
            arr[i] = Integer.parseInt(st.nextToken());      
            dp[i] = arr[i];      
        }

        int answer =0;

        for(int i=0;i<n;i++)    //기준값
        {
            for(int j=0;j<i;j++)    //비교값
            {
                if(arr[i]> arr[j]) //값이 증가하면 더하기
                {                  
                    dp[i] = Math.max(dp[i], dp[j]+arr[i]);                   
                }
            }
            
            answer = Math.max(dp[i],answer);

        }
        
        System.out.println(answer);

    }
}