[BOJ/DP] 백준 11055 - 가장 큰 증가하는 부분 수열 / 11053 - 가장 긴 증가하는 부분 수열 (Java)

11055 - 가장 큰 증가하는 부분 수열

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

문제

ex. 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우
합이 가장 큰 증가하는 부분 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}

=> 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것 ?

입력
첫째 줄: 수열 A의 크기 N (1 <= N <= 1,000)
둘째 줄: 수열 A를 이루고 있는 $A_i$ (1 <= $A_i$ <= 1,000)
출력: 수열 A의 합이 가장 큰 증가하는 부분 수열의 합

---

풀이

• `dp[i] = A[i]` => 자기 자신 포함
  • `dp[i]`: i번째 원소를 마지막으로 하는 증가 부분 수열의 최대 합
• `dp[i] = Math.max(dp[i], dp[j] + A[i])`
  • `dp[j]`: A[0] ~ A[j]까지 누적합 = 앞에서 나보다 작은 것들 중 가장 큰 것
    / `A[i]`를 붙이면 -> `dp[j] + A[i]`

---

코드

// 가장 큰 증가하는 부분 수열
public class boj_11055 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        int[] dp = new int[N];

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

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

        System.out.println(max);
    }
}

---

11053 - 가장 긴 증가하는 부분 수열

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

문제

ex. 수열 A = {10, 20, 10, 30, 20, 50} 인 경우
합이 가장 큰 증가하는 부분 수열 A = {10, 20, 10, 30, 20, 50}, 길이 4

=> 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열 ?

입력
첫째 줄: 수열 A의 크기 N (1 <= N <= 1,000)
둘째 줄: 수열 A를 이루고 있는 $A_i$ (1 <= $A_i$ <= 1,000)
출력
: 수열 A의 가장 긴 증가하는 부분 수열의 길이

---

풀이

• `dp[i] = 1` => 자기 자신 포함
  • `dp[i]`: `A[i]`를 마지막 원소로 하는 증가 부분 수열의 최대 길이
    = `A[i]`가 맨 끝에 있을 때, 앞에서부터 어떤 증가 수열 만들 수 있는지
• `dp[i] = Math.max(dp[i], dp[j] + 1)` => 예제 확인
  • `dp[j]`: A[0] ~ A[j]까지 LIS 길이/ A[i]를 붙이면 -> `dp[j] + 1`

---

예제

A = [10, 20, 10, 30]

dp = [1, 1, 1, 1] // 자기 자신

• i = 1 (A[1] = 20)
  • j = 0
    • A[0](10) < A[1](20) => O
      • dp[1] = max(dp[1](1), dp[0](1) + 1) = 2
  • => dp = [1, 2, 1, 1]
• i = 2 (A[2] = 10)
  • j = 0 
    • A[0](10) == A[2](10) => X
  • j = 1
    • A[1](20) > A[2](10) => X
  • => dp = [1, 2, 1, 1]
• i = 3 (A[3] = 30)
  • j = 0
    • A[0](10) < A[3](30) => O
      • dp[3] = max(dp[3](1), dp[0](1) + 1) = 2
  • j = 1
    • A[1](20) < A[3](30) => O
      • dp[3] = max(dp[3](2), dp[1](2) + 1) = 3
  • j = 2
    • A[2](10) < A[3](30) => O
      • dp[3] = max(dp[3](3), dp[2](1) + 1) = 3
  • => dp = [1, 2, 1, 3]

=> 최댓값: 3 (10 -> 20 -> 30)

---

코드

import java.io.*;
import java.util.*;

// 가장 긴 증가하는 부분 수열
public class boj_11053 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        int[] dp = new int[N];

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

        int max = 1;

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

        System.out.println(max);
    }
}