[JAVA]백준 11722번: 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

 

 

 

 

 

 

이 문제는 백준 11053번 가장 긴 증가하는 부분 수열을 풀고 for문 조건만 수정해서 제출했다. 

 

11053_가장 긴 증가하는 부분 수열 해설법

https://hailey-v.tistory.com/9

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

 

 

| 문제 해결방법

 

 

 

아이디어는 위 해설법과 같고 수정된 부분은

 

앞의 문제가 0번째 index부터 LIS를 돌렸다면,

이 문제는 가장 긴 감소하는 부분 수열이기 때문에 마지막 index부터 LIS를 돌리면

앞의 문제와 동일할 것 같다는 생각이 들었다.

 

그래서 for문의 index 시작점, 끝점만 수정해주었다. 

 

 

 

[JAVA] 해설 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] arr;
	static int[] dp;
	static int A;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		A = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[A];
		dp = new int[A];
		
		//Arrays.fill(dp, -1);
		for(int i=0;i<A;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 마지막 index부터 LIS 수행 
		for(int i=A-1;i>=0;i--) {
			LIS(i);
		}
		
		int max = -1;
		for(int i=0;i<A;i++) {
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);
		
	}
	private static int LIS(int N) {
		
		if(dp[N]==0) {
			dp[N]=1; 
			
            // 현재 index부터 마지막 index까지 검사
			for(int i=N;i<A;i++) {
				if(arr[N] > arr[i]) {
					dp[N] = Math.max(dp[N], LIS(i)+1);
				}
			}
		}
		

		return dp[N];
		
	}
	
}

 

 

 

[제출] 메모리 및 시간