[백준] 2631 - 줄세우기

[백준] 2631 - 줄세우기

[문제링크]

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 lcs=0; for (int i = 0; i < N; i++) { int max=0; for (int j = 0; j < i; j++) { if(num[j] < num[i] && max

결과 화면

from http://nato-blog.tistory.com/151 by ccl(S) rewrite - 2021-11-15 03:01:37