백준 11053 자바 - 가장 긴 증가하는 부분 수열

문제

---

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

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

 

 

 

문제해결

---

- dp 배열을 만들어 0~N번째 까지 가장 긴 수열의 개수를 담는다

- 어떤 숫자로도 수열을 만들면 개수가 1이므로 dp는 1로 초기화 한다

- 2중 반복문을 돌면서 i번째 숫자와 0~i번째 숫자를 비교하며 가장 긴 수열의 길이를 dp에 담는다

- i번째 숫자가 j번째 숫자보다 큰 경우 여태까지 만들 수 있었던 수열중 가장 긴 수열 길이와 j번째 까지의 긴 수열에 i를 추가한 수열의 길이 중 큰 값을 dp에 담는다

- 전체를 돈 후 dp 중 가장 큰 값이 가장 긴 수열 길이다

import java.util.Scanner;

public class B11053_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1; //dp 배열 1로 초기화
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j])//i번째 숫자가 j번째 숫자보다 큰 경우에만 dp 배열을 비교해본다
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    //dp[i] : 현재 i번째 까지 가장 긴 수열 길이
                    //dp[j] + 1 : j번째 까지 가장 긴 수열 길이에 i를 추가한 수열의 길이
                    //위 2개중 더 긴 값을 dp에 담는다
            }
        }
        //dp 중 가장 큰 값이 가장 긴 수열의 길이
        int result = 0;
        for (int i : dp)
            result = Math.max(result, i);
        System.out.println(result);
    }
}