0. 아이의 위치를 최소한으로 바꾸면서 순서를 정렬하는 방법 = 이미 정렬된 가장 긴 문자열을 찾고, 그 나머지를 이동하면 된다
가장 긴 증가하는 부분 수열(LIS)을 구하면 된다
1. DP를 통해 이전까지 진행한 결과들 중 현재 순서보다 작으면서 그 값이 제일 큰 값을 구한다
2. 해당 값 +1이 현재 지점까지의 LIS이다
3. LIS를 마지막까지 구한 후, 가장 큰 LIS 길이를 구한다
4. 해당 LIS에 속하지 않는 아이들을 이동하면 된다. 즉, (전체 아이 수 - LIS길이) = (이동해야하는 아이 수)
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = pint(br.readLine());
int[] num = new int[N];
int[] dp = new int[N];
for (int i = 0; i < N; i++) {
num[i]=pint(br.readLine());
}
int lis=0;
for (int i = 0; i < N; i++) {
int max=0;
for (int j = 0; j < i; j++) {
if(num[j] < num[i] && max<dp[j])max=dp[j];
}
dp[i]=max+1;
lis = Math.max(dp[i], lis);
}
System.out.println(N-lis);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Integer[] tmp = new Integer[26];
int N = pint(br.readLine());
int num=9, sum=0;
for (int i=0; i<26; i++)tmp[i]=0;
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < s.length(); j++)tmp[s.charAt(j)-'A']+= (int)Math.pow(10, s.length()-j-1);
}
Arrays.sort(tmp, Comparator.reverseOrder());
for (int i = 0; i < 10; i++)sum+=tmp[i]*num--;
System.out.println(sum);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
