문제
N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.
또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.
예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.
이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.
구현코드
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
ArrayList<Integer>list = new ArrayList<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < n ; i++){
list.add(Integer.parseInt(st.nextToken()));
}
Collections.reverse(list);
int[] dp = new int[n];
Arrays.fill(dp, 1);
for(int i = 1 ; i < n ; i++){
for(int j = 0; j < i; j++){
if(list.get(i) > list.get(j)){
dp[i] = Math.max(dp[j] +1, dp[i]);
}
}
}
int maxValue = 0;
for (int i = 0; i < n; i++) {
maxValue = Math.max(maxValue, dp[i]);
}
System.out.println(n - maxValue);
}
}코드해석
이 문제는 최장 증가 부분 수열(LIS) 알고리즘을 이용해야하는 문제이다. dp 문제는 정말로 사고력을 필요로하는 문제와 알고리즘을 알고있어야 풀 수있는 문제로 나누어 지는거 같다.
즉 문제를 많이풀어본 사람이 유리한 것은 맞는것이다.
최장 증가 부분 수열은 오름차순으로 보면서 각각을 반복하며 오름차순으로 정리가 되어있는 최대를 구하면 되는 문제이다.
만약 1 5 4 2 3 8 9 5 4 7 이라는 배열이있다고 가정하자. 8까지의 최장 증가 부분 수열은
1. 1에서 끝나는 경우 : 1
2. 5에서 끝나는 경우 : 1 5
3. 4에서 끝나는 경우 : 1 4
4. 2에서 끝나는 경우 : 1 2
5. 3에서 끝나는 경우 : 1 2 3
즉 최대 값임 1238 이 된다고 볼 수 있다.
이 것을 dp 로 나타내면 된다.
for(int i = 1 ; i < n ; i++){
for(int j = 0; j < i; j++){
if(list.get(i) > list.get(j)){
dp[i] = Math.max(dp[j] +1, dp[i]);
}
}
}