[Baekjoon] 11053번 : 가장 긴 증가하는 부분 수열

1. 문제

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

• DP, LIS 문제

# 문제
수열 A가 주어졌을 때,
가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에
가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고,
길이는 4이다.

# 입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

# 출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

# 예제 입력 1
6
10 20 10 30 20 50

# 예제 출력 1
4

2. 핵심 아이디어

• 전형적인 DP 문제
• 수열의 크기가 N일 때, 기본적인 DP 알고리즘으로 O(N^2)에 해결할 수 있음
• D(i) = arr(i)를 마지막 원소로 가지는 부분 수열의 최대 길이
• 모든 0 <= j < i 에 대하여, D(i) = max(D(i), D(j) + 1) if arr(i) < arr(j)

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [1] * n

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

print(max(dp))

4. Java 문제풀이

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

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[0] = 1;

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

    int max = 0;
    for (int i : dp) {
      max = Math.max(max, i);
    }
    System.out.println(max);
  }
}