BOJ_11053 : 가장 긴 증가하는 부분 수열

👉 문제링크

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

---

---

🔸 문제 분석 🔸

• n개의 수열을 입력받고, 가장 긴 증가하는 부분 수열의 길이를 출력한다.
• 수열의 인덱스 별 부분 수열 길이의 최대값을 저장하는 dp배열을 만들어 값을 구한다.
  • 각 인덱스의 수가 부분 수열의 마지막 수가 됐을 때를 계산해서 그 중 최대값을 구해야 한다.
    • 각 인덱스의 앞쪽에서 수열 원소값이 더 작은 것들 중 dp배열 값이 가장 큰 값을 구한다.
    • 구한 값에 +1해서 현재 인덱스의 dp배열 값으로 저장한다.
  • 수열의 순서는 변경할 수 없다. (정렬하지 않는다.)
  • 마지막 인덱스의 부분 수열 값이 무조건 최대값인건 아니다.
  • 예제 수열에 적용해 dp배열을 구해보면 다음과 같다.
    • 0번 인덱스 '10'은 만들 수 있는 부분 수열의 최대 길이가 1이다.
    • 1번 인덱스 '20'은 '10'-'20' 으로 2이다.
    • 2번 인덱스 '10'은 1이다.
    • 3번 인덱스 '30'은 '10'-'20'-'30' 으로 3이다.
    • 4번 인덱스 '20'은 '10'-'20'으로 2다.
    • 5번 인덱스 '50'은 '10'-'20'-'30'-'50'으로 4이다.
    • 따라서 인덱스 0-1-3-5가 가장 긴 증가하는 부분 수열이다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            dp[i] = 1;
        }

        int max = 0;

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

🔸 코드 해석 🔸

• n 크기의 수열을 입력받을 배열 arr와 dp배열을 선언하고 값을 넣는다.
  • dp배열의 초기값은 1이다. (수열이 내림차순인 경우 모두 1이나옴)
• max는 dp 배열의 최대값을 저장하는 변수
• arr배열의 0번 인덱스부터 n-1 인덱스 까지 수열의 마지막으로 두고 계산 해보며 dp배열을 채운다.
  • arr[0]부터 arr[i-1] 까지 중 arr[i]보다 값이 작은 것들 중 dp배열의 값이 최대인 값을 구한다.
    • dp[i]가 크다면 유지, dp[j]+1이 더 크다면 변경한다.
  • max도 검사해서 업데이트한다.
• max값을 출력한다.

---

🔸 end 🔸

• '가장 긴 증가하는 부분 수열' 의 뜻을 이해하지 못해서 질문 게시판을 참고했다.
• 난 처음 봤지만 시리즈가 많은 것을 보니 dp문제로 많이 나오는 듯 하다.