[백준] 11568 민균이의 계략 - 동적계획법(Dynamic Programming, DP) + LIS(Longest Increasing Subsequence) JAVA

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

코드설명

동적계획법(Dynamic Programming, DP) + LIS(Longest Increasing Subsequence) 를 활용합니다.

 

문제의 설명을 읽다보면, LIS 의 값을 구하라는 것을 알 수 이습니다.

동적계획법을 사용안한다면, 완전탐색으로 1000 ! 의 시간복잡도가 나올 수 있음을 알 수 있습니다.

코드

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;
	}
	
}