다이나믹 프로그래밍_10844 : 가장 긴 감소하는 부분 수열 JAVA

가장 긴 감소하는 부분 수열 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

34867

21614

17754

62.953%

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 30 10 20 20 10

예제 출력 1 복사

3

 

다이나믹 프로그래밍 Buttom-up 방식으로 풀었다.

수열 A가 주어졌을때, 가장 긴 감소하는 부분 수열을 구하는 문제이다. 

 

먼저 배열 A[1], A[2], A[3]을 보게 되면, A[2]보다 A[3]가 작기 때문에 D[3] 값을 D[2]+1로 해준다.

 

두번째로 A[4]를 진행한다. A[4] 값은 A[2]보다는 작지만 A[3]보다는 크기 때문에 D[4]값은 2를 갖는다.

 

세번째로 A[5]를 진행한다. A[5]는 A[4]와 동일하므로 D[5]는 2를 갖는다.

네번째로 A[6]를 진행한다. A[6]는 A[5]보다 작으므로 D[6]는 D[5]+1값을 갖는다.

 

 

import java.io.*;
import java.util.*;

public class Main{
    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];
        int[] dp = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken()); // 배열담기
        }
        
        for(int i=0;i<N;i++){
            dp[i] = 1;
            for(int j=0;j<i;j++){
                if(arr[i]<arr[j]&&dp[i]<=dp[j]) // 배열 최신값이 이전 값보다 작고, dp 최근값이 이전값들보다 작거나 같다면 DP 이전값에서 +1해준다
                    dp[i] = dp[j]+1;
                
                else if(arr[i]==arr[j]) // 배열 최신값과 그 이전값이 동일하다면 dp값도 동일하게 한다.
                    dp[i] = dp[j];
            }
        }
        int max = 0;
        for(int i=0;i<N;i++){
            max = Math.max(dp[i],max); // dp Max값 뽑기
        }
        System.out.println(max);
    }
}