[백준] 11722 가장 긴 감소하는 부분 수열 - 동적계획법(Dynamic Programming, DP) + LDS(Longest Decreasing Subsequence) JAVA

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

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

코드설명

DP와 LDS(Longest Decreasing Subsequence) 문제입니다.

 

우리가 구하는것은 각 위치에서의 수열의 감소하는 부분 수열의 개수이므로

6
10 30 10 20 20 10
 
dp[] =  1 1 2 2 2 3

 

위의. 로직을 구현해보았습니다.

 

처음에 DP값은 위의 로직을 구현하였지만, 가장 긴 감소하는 부분 수열을 구하는 과정에서 단순히 

dp[N] 값을 출력함으로써 틀렸습니다.

아래와 같이 모든 dp값을 순회하면서 answer값을 갱신해야합니다.

for(int i=0;i<N;i++) {
    answer = Math.max(dp[i], answer);
}

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int[] dp;
	public static int[] arr;
	public static int answer;
	public static int MOD = 10007;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N];
    	arr = new int[N];
    	
    	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] = Math.max(dp[i], dp[j] + 1);
    			}
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		answer = Math.max(dp[i], answer);
    	}
    	System.out.println(answer);
    	
    }
}

 

재귀와 메모이제이션을 활용한 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int[] arr;
	static int answer = 0;
	static int[] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		cache = new int[N+1];
		Arrays.fill(cache, -1);
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(LIS(-1) - 1);
	}
	
	static int LIS(int now) {
		
		if(cache[now + 1] != -1) return cache[now+1];
		int ret = 1;
		for(int next = now + 1; next < N; next++) {
			if(now == -1 || arr[now] > arr[next]) {
				ret = Math.max(ret, LIS(next) + 1);
			}
		}
		return cache[now + 1] = ret;
	}
	
}