[백준/S2/DP/자바] 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다. ( 시간 제한 1초 )

 

---

 

풀이 방법

 

DP 문제 입니다.

 

dp[i] =  i번째 인덱스 까지 만들수 있는 가장 긴 증가 하는 부분 수열 입니다.

dp[i] = 1로 초기화 ( 가장 작은 부분 수열 길이가 1 )

 

코드와 예시로 보는 편이 이해가 빠를 듯 합니다.

ex) arr = new int {3, 1, 5, 2, 4}

 

 

i -> i 번째 인덱스를 마지막 으로 하는 ( 증가 하는 부분 ) 수열을 만들때,

j -> 부분 수열이 되는 수를 찾는다.

 

ex) 3번째 인덱스인 5를 마지막 으로 하는 부분 수열을 찾을 때 :

1, 2 번째 인덱스 중에서 부분 수열의 요소를 찾습니다.

 

dp[1] / dp[2]

dp[1] = 1;

dp[2]
arr[2] = 1
앞부분 (j = 1; j < 2;) 자신의 부분 수열이 없으 므로 dp[2] = 1

 

dp[3]

arr[3] = 5
앞부분 (j = 1; j < 3;) 3,1은 부분 수열이 된다.
dp[3] = Math.max(1, dp[1] + 1)
dp[3] = Math.max(2, dp[2] + 1)
dp[3] = 2

 

dp[4]

dp[4] (j = 1; j < 4;) 1은 2의 부분 수열이 된다.
dp[4] = Math.max(1, dp[2] + 1)
dp[4] = 2

 

dp[5]

dp[5] (j = 1; j < 5;) 3,1,2는 4의 부분 수열이 된다.
dp[5] = Math.max(1, dp[1] + 1)
dp[5] = Math.max(2, dp[2] + 1)
dp[5] = Math.max(2, dp[4] + 1)
dp[5] = 3

 

 

 

---

 

전체 코드

public class LongestSubsequence11053 {
    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 + 1];
        int[] dp = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int index = 1;

        while(st.hasMoreTokens()){
            arr[index] = Integer.parseInt(st.nextToken());
            dp[index] = 1;
            index++;
        }

        int maxLength = 1;

        for(int i = 1; i < arr.length; i++){
            for(int j = 1; j < i; j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    maxLength = Math.max(maxLength, dp[i]);
                }
            }
        }
        System.out.println(maxLength);
    }
}