[Java] 백준 11053 - 가장 긴 증가하는 부분수열

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

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

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

해결방법

• DP로 해결한다
  • dp[i] 는 주어진 배열의 i 번째, 즉 arr[i] 를 마지막 원소로 하는 증가하는 수열의 길이이다.
• setDp(k) 메서드는 dp[k]의 값을 구해서 반환해준다.
  • 따라서 재귀호출되는 setDp(k - 1)은 마지막에 arr[k] 요소를 붙일 수 있는 여러 배열 중 가장 긴 배열의 길이 길이를 반환할 것이고, + 1을 해주면 dp[k]가 되는 것이다.

코드

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

public class Baekjoon_11053 {

    static Integer[] dp;
    static int[] arr;

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

        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        dp = new Integer[n];

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

        for (int i = 0; i < n; i++) {
            setDp(i);
        }

        int max = dp[0];

        for (int i = 0; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }

    public static int setDp(int n) {
        if (dp[n] == null) {
            dp[n] = 1;

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