백준 | DP 섹션 - 11053번. 가장 긴 증가하는 부분 수열 문제 풀이

23.04.06 문풀

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

import java.util.Scanner;

/* 11053번. 가장 긴 증가하는 부분 수열  */
public class Main {
    static int[] dy;

    //솔루션 함수 
    public int solution(int[] arr) {
        int answer =0;
        dy = new int[arr.length];

        dy[0] =1;
        answer = dy[0];

        for(int i=1; i<arr.length; i++) {
             int max = 0;
             for(int j=i-1; j>=0; j--) {
                 if(arr[i]> arr[j] && dy[j] > max) max = dy[j];
             }
             dy[i] = max+1;
             answer = Math.max(answer, dy[i]);
        }
        return answer ;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        int n= kb.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(arr));

    }
}

---