[Baekjoon] 11055번 : 가장 큰 증가 부분 수열

1. 문제

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

• DP 문제

// 문제
수열 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

2. 핵심 아이디어

• O(n^2) 시간 정도의 알고리즘 설계하여 해결
• 수열에서 자신보다 앞 쪽에 있는 값 중 자신보다 작은 값의 인덱스를 찾음
• 해당 인덱스의 dp 값중 가장 큰 값과 자신의 값을 더해 dp를 채움
• dp에서 max값을 출력

3. Python 문제풀이

import copy
import sys
input = sys.stdin.readline

n, a = int(input()), list(map(int, input().split()))

# dp[i] : i 까지 왔을 때, 합의 최대
dp = copy.deepcopy(a)

for i in range(1, n) :
  for j in range(i) :
    if a[i] > a[j] :
      dp[i] = max(a[i] + dp[j], dp[i])

print(max(dp))

4. Java 문제풀이

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

class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] a = new int[n+1];
    int[] dp = new int[n+1];

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

    for (int i=1; i<=n; i++) {
      a[i] = Integer.parseInt(st.nextToken());
    }

    dp[1] = a[1];
    int result = dp[1];

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