[백준] 11053 가장 긴 증가하는 부분 수열 - 동적계획법(Dynamic Programming, DP) + LIS(Longest Increasing Subsequence) JAVA

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

11053번: 가장 긴 증가하는 부분 수열

코드설명

DP와 LIS(Longest Increasing Subsequence) 문제입니다.

 

처음에 

 A = {10, 20, 10, 30, 20, 50} 가 있을때

dp[] = {10, 20, 20, 30, 30, 50} 이런식으로 갱신하여서 for문으로 값이 변화하는 구간을 찾아서 진행하려고 하였지만

 

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

A = {10, 20, 10, 30, 20, 50} 이 있을때

dp[] = {1, 2, 1, 3, 2, 4} 이런식으로 구하는것이 더 적합합니다.

 

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

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static int T, N, M;
	public static int answer = 1;
	public static int[] arr;
	public static int[] dp;
    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+1];
    	dp = new int[N+1];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    
    	for(int i=1;i<=N;i++) {
    		dp[i] = 1;
    		for(int j=1;j<i;j++) {
    			if(arr[j] < arr[i]) {
    				dp[i] = Math.max(dp[i], dp[j]+1);
    			}
    		}
    	}
    	
    	for(int a : dp) {
    		answer = Math.max(answer,  a);
    	}
    	System.out.println(answer);
    }
    
}

 

재귀와 메모이제이션을 활용하여 아래와 같이도 가능합니다.

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 answer = 0;
	static int[] arr;
	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;
	}
	
}

위의 코드 구현하면서 실수했었던점은... 아래와 같이 now + 1 로 현재 위치의 다음 칸부터 비교해야하는데, next = 0 으로 시작하여서 잘못된 결과가 나왔었습니다.

for(int next = now + 1; next < N; next++) {
    if(now == -1 || arr[now] < arr[next]) {
        ret = Math.max(ret, LIS(next) + 1);
    }
}