백준 11053[자바] java 가장 긴 증가하는 부분 수열

문제 링크: https://www.acmicpc.net/problem/11053

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

---

▶해설

(브루트 포스로 문제를 접근하니 시간 초과가 떴습니다.)

 

Dynamic Programming으로 풀었습니다. 

 

1. arr 배열에 입력을 받습니다.

2. i는 1부터 증가하여 하나씩 dp를 완성해가는 변수입니다.

3. j는 0부터 시작하여 i보다 작게 접근합니다.

 

 

arr [i]가 arr [j]보다 크다면 arr [j]와 arr [i]는 증가수열입니다. 

 

dp [j]는 arr [j]까지 하여금 가장 긴 수열의 길이를 가지고 있습니다. 

 

따라서 arr[i]>arr[j] && dp [j]>=dp [i]를 만족한다면 dp [j]까지의 증가수열 + 현재의 arr [i]까지 증가하는 수열을 만족합니다. ->  dp [i]=dp [j]+1 됩니다.

 

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


public class Main {

    static int [] arr;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];

        String[] s = br.readLine().split(" ");

        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(s[i]);
        }

        int [] dp = new int[n];
        dp[0]=1;
        for(int i=1; i<n; i++){
            dp[i]=1;
            for(int j=0; j<i; j++){
                if(arr[i]>arr[j] && dp[j]>=dp[i]){
                    dp[i]=dp[j]+1;
                }
            }
        }
        Arrays.sort(dp);
        System.out.println(dp[n-1]);
    }
}