[백준] 18353 병사 배치하기 - 동적계획법(DP, Dynamic Programming) + LDS(Longest Decreasing Subsequence) JAVA

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

18353번: 병사 배치하기

코드설명

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

LIS 대신에 Longest Decreasing Subsequence 를 활용합니다.

 

모든 병사를 배치할때 가장 긴 감소하는 부분 수열을 구합니다.

이때, 문제의 예를 보면 아래와 같습니다.

입력
7
15 11 4 8 5 2 4

DP 출력
 1 2 3 3 4 5 5
 
결과
2

 

 

LDS를 구함으로써 우리는 해당 병사들을 올바르게 배치했을때의 가장 큰 최적의 길이를 구하기에,

N값에서 그 값을 뺴면 병사의 길이가 나옵니다.

 

코드

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

public class Main {
	public static int T, N;
	public static int[] arr = new int[2001];
	public static int[] dp = new int[2001];
	public static int answer = 0;
	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());
    	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]) { //더 작을경우 1개씩 증가시킨다.
    				dp[i] = Math.max(dp[i], dp[j] + 1);
    			}
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
//    		System.out.print( " "+dp[i]);
    		answer = Math.max(answer,  dp[i]);
    	}
    	System.out.println(N - 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, M, S, P, K, A, B, X;
	static int answer = 0;
	static int[] cache = new int[2002];
	static int[] arr = new int[2001];
	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());
		st = new StringTokenizer(br.readLine());
		Arrays.fill(cache, -1);
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(N - ( LDS(-1) - 1 ));
	}
	
	static int LDS(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, LDS(next) + 1);
			}
		}
		return cache[now + 1] = ret;
	}
}