[백준] 자바 Java, 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

알고리즘 분류

• 다이나믹 프로그래밍

 

나의 풀이

참고)

[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]

• Bottom-up 방식 사용

package level15_dynamicProgramming;

import java.util.Arrays;
import java.util.Scanner;

//백준 11053번 문제] 가장 긴 증가하는 부분 수열
public class Backjoon11053 {
    public static void main(String[] args) {
        //입력strat
        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();
        }
        //입력end

        //dp
        for(int i=0; i<n; i++) {
            dp[i] = 1;

            // 각 자리마다(i) 0부터 i 이전까지의 원소 비교!
            for (int j=0; j<i; j++) {
                // j번째 원소보다 작으면서 && dp[i]가 dp[j]+1(초기값이 1이기 때문에)보다 작은 경우
                if(arr[j] < arr[i] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }

        }

        //최댓값 구하기
        Arrays.sort(dp);
        System.out.println(dp[n-1]);
    }//main end
}

 

결과

배열 인덱스 항상 주의,,, 오타 주의,,,