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

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

11055번: 가장 큰 증가하는 부분 수열

코드설명

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

 

이전에 11053 가장 긴 증가하는 부분 수열과 비슷한 문제입니다.

해당 문제는 이전에 

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

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

dp[] = {1, 2, 1, 3, 2, 4} 이런식으로 구했었습니다.

 

이번에는 dp값에 긴 증가하는 부분 수열을 넣지않고,

dp값에 각 위치에서의 증가하는 부분 수열들의 합 을 넣습니다.

 

예로들면

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

dp[] = {10, 30, 10, 60, 30, 110} 이런식으로 될 것입니다.

 

문제의 예시로보면

10
1 100 2 50 60 3 5 6 7 8

dp[] =  {1, 101, 3, 53, 113, 6, 11, 17, 24, 32 }

 

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

코드

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 = 0;
	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];
    	dp = new int[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp[0] = 1;
    	for(int i=0; i<N;i++) {
    		dp[i] = arr[i];
    		for(int j=0;j<i;j++) {
    			if(arr[i] > arr[j]) {
    				dp[i] = Math.max(dp[i], dp[j] + arr[i]);
    			}
    		}
    	}
    	
    	
    	for(int i=0;i<N;i++) {
    		answer = Math.max(answer,  dp[i]);
    	}
    	
    	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));
		
	}
	
	static int LIS(int now) {
		
		if(cache[now+1] != -1) return cache[now+1]; 
		int ret = 0;
		for(int next = now + 1; next < N; next++) {
			if(now == -1 || arr[now] < arr[next]) {
				ret = Math.max(ret, LIS(next) + arr[next]);
			}
		}
		
		return cache[now+1] = ret;
	}
	
}

 

이떄,아래와 같이 arr[next]를 + 하는 이유는, now값을 -1 로 시작하기에 -1 값은 신경쓰지 않아도되기 때문입니다.

만약에 now값이 0, 1, 2, 3... N-1 으로 시작하도록 함수를 처리했다면, 현재 값도 더해주어야 하니 arr[now]로 변경되어야하겠지요.

ret = Math.max(ret, LIS(next) + arr[next]);