99클럽 코테 스터디 31일차 TIL DP(줄세우기)

https://www.acmicpc.net/source/86922116

 

알고리즘의 난이도가 올라가면 더 이상 알고리즘 난이도의 문제가 아닌 아이디어의 문제임을 알려주는 대표적인 유형의 문제.

 

<아이디어>

별의별 생각을 다 해보며 규칙을 찾아봤는데 결국은 하나였다. 오름차순으로 만들어야 한다는 것.

오름차순으로 만들기 위해 옮겨지는 아이의 최소 수는? 이미 오름차순인 번호를 제외하고, 나머지 번호를 옮겨주면 된다.

즉, (총 학생 수 - 가장 긴 증가하는 부분 수열) 인 것이다~!

가장 긴 증가하는 부분 수열은 이전에 넘 많이 글을 올렸어서 링크로 첨부하겠당.

https://dev-zsunny.tistory.com/65

99클럽 코테 스터디 30일차 TIL DP(상자넣기)

https://dev-zsunny.tistory.com/62

99클럽 코테 스터디 28일차 TIL DP(가장 큰 증가하는 부분 수열)

https://dev-zsunny.tistory.com/61

99클럽 코테 스터디 27일차 TIL DP(가장 긴 감소하는 부분 수열)

제출 코드는 아래와 같다!

 

<제출코드>

package Study.Week05;

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

public class Day31_BOJ_2631_줄세우기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                if(arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            ans = Math.max(ans, dp[i]);
        }
        // 오름차순이 아닌 학생 수
        System.out.println(n - ans);
    }
}