[백준][JAVA] 11055 - 가장 큰 증가하는 부분 수열 - DP

📌 문제

백준 | 가장 큰 증가하는 부분 수열 | SILVER 2 | DP

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

 

📌 문제 탐색하기

• 증가하는 부분 수열 중, 합이 가장 큰 것 구하기

ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}

⇒ 1,2,50,60 = 113

⇒ 3, 5, 6, 7, 8 = 29

그러므로 가장 큰 증가하는 부분 수열은 113

 

 

📌 알고리즘

• 부분수열을 구해야하는데, A의 크기가 1,000까지 가능
• 만약 for문을 통해 돌 경우, 1000 * (1000 - i) (i = 자신의 위치)
  • 시간이 1초제한이므로, 1000000 - 1000i라 가능할 것 같긴한데.. => 너무 비효율적인 것 같아서 PASS
• 어쨌든, 최대 합인 부분수열을 골라야하므로, DP문제
• 만약에 1, 100 이러면 101로 끝내버림
  • ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
    • DP[0] = 1
    • DP[1] = 101
    • DP[2] = 3
    • DP[3] = 53
    • DP[4] = 113
    • DP[5] = 6
    • DP[6] = ~

→ 즉, 자기자신 + 자신의 앞에있는 수들 중 자기보다 작은 값의합 들 중 최댓값 구하기

• 1회차 풀이 이후, 점화식을 세워봐야겠다고 고민하게 됨
• DP[i] = A[i]
• DP[i] = Math.max(DP[i], A[i] + DP[i-1 ~ 0]);

 

 

📌 코드 설계하기

1. a 크기 및 a 배열 입력받기
2. 증가하는 부분수열 메소드 정의하기

 

 

📌 시도 회차 수정 사항

1회차

• 백준의 예제 자체는 맞고, 1차때 생각한 풀이대로는 풀었음
• 근데 풀어놓고 보니, 이건 점화식을 세워서 푼 ‘정석 DP 풀이’는 아니라고 느껴졌음…
• 차라리 아예 MAX를 활용해서 아예 DP 배열에 있는 숫자들로 덧셈을 하는 걸로 구현해야할 것이라 생각

## 틀린 코드 ##
import java.util.*;
import java.io.*;

public class q11055_silver2 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int answer = 0;

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

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

 

📌 2회차 정답 코드

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));
        StringTokenizer st;
        int answer = 0;

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

        for(int i = 0; i<n; i++){
            dp[i] = arr[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(answer, dp[i]);
        }

        System.out.println(answer);
    }
}

 

 

오,, 그래도 DP를 꾸준히 풀다보니 점점 윤곽이 잡히는 것 같아 기분 좋게 풀 수 있었다 .. ㅎㅎ

백준에 증가 부분 수열 시리즈 있는데 다 풀면서 DP에 대한 지식 쌓아야겠다 !!!