[백준,BOJ 11722] 가장 긴 감소하는 부분 수열(JAVA 구현)

 

-내 생각

  이전 글에서 작성했던 가장 긴 증가하는 부분 수열 문제와 동일한 문제라고 생각했다. 원래 이 문제는 단계별 풀어보기 동적 계획법 1에 존재하지 않는 문제인데, 풀게 된 계기는 11054번 문제인 가장 긴 바이 토닉 부분 수열 문제를 해결하기 위해서 먼저 풀어보면 좋다고 하여 풀어보게 되었다.

 

-해법

  이 문제는 가장 긴 증가하는 부분 수열 문제와 알고리즘은 완전히 동일하며 반복문 부분만 수정해주면 된다. 즉 시작 인덱스를 1이 아닌, n부터 시작하면 되는 것이다. 자세한 것은 코드를 보자.

 

import java.util.*;

public class Main {
	static int n;
	
	static int dp[], cost[];
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		dp = new int[n+1];
		cost = new int[n+1];
		
		for(int i=1;i<=n;i++) {
			cost[i] = sc.nextInt();
		}
	
		dp[n] =1; // 뒤에서 부터 증가하는 부분 수열을 찾는다. 
		
		for(int i=n-1;i>0;i--) { // 반복문의 조건들만 변경해주면 된다.
			dp[i] =1;
			for(int j=n;j>0;j--) {
				if(cost[i]>cost[j]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
				}
			}
		}
		
		int max = Integer.MIN_VALUE;
		for(int i=1;i<=n;i++) {
			if(dp[i]>max) {
				max = dp[i];
			}
		}
		
		System.out.println(max);
		
			
			
		
	}
	
}