백준 병사 배치하기

병사 배치하기

LIS(최장 길이 부분수열) 문제이다. ArrayList로 받아 방향을 변경 해 내림차순으로 바꿔 메모아이제이션으로 배치 최대값을 구하고 N에서 뺀다. 시간 복잡도가 O(N^2)롷 구현했고 O(NlogN)로 더 빠른 풀이법이 있다는데 패스.. 다른 블로그를 참고했다. dp는 너무 어렵다..

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		List<Integer> soldiers  = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			soldiers.add(sc.nextInt());
		}
		
		Collections.reverse(soldiers);
	
		int[] dp = new int[N];
		
		Arrays.fill(dp, 1);
		
		
		for(int i = 1; i < N; i++) {
			for(int j = 0; j < i; j++) {
				if(soldiers.get(i) > soldiers.get(j)) {
					dp[i] = Math.max(dp[i], dp[j] + 1);					
				}
			}
		}
		
		int maxValue = 0;
		
		for(int i = 0; i < N; i++) {
			maxValue = Math.max(maxValue, dp[i]);
		}
	}

}