백준 2631 & 7570 줄 세우기 Java

백준 2631 줄세우기

---

백준 7570 줄 세우기

문제는 간단하면서도 나에게는 어려운 문제들이다. dp로 풀지않더라도 풀 수 있는 문제들이지만

dp로 푸는 것이 더 간단하다고 생각이 들어 정리 하려고 한다.

 

2631번 문제와 7570문제는 같은 듯 하면서도 다른 문제이다.

 

2631번 문제의 경우엔

5 2 4 1 3 등 마구잡이로 주어진 수에서

수를 아무렇게나 옮겨서 정렬된 배열을 만들 때 최소 횟수이고

 

7570번 문제의 경우엔

5 2 4 1 3 등 마구잡이로 주어진 수에서

수를 맨 앞이나 맨 뒤로만 옮겨서 정렬된 배열을 만들 때 최소 횟수이다.

 

이 문제 들은 가장 긴 증가수열 알고리즘(LIS)을 활용해서 해결하면 된다.

사실 문제들을 보고 가장 긴 증가수열 알고리즘을 활용해서 풀어야 된다는 사실을 깨닫지 못했다.

 

2631번 문제의 경우엔 수를 아무곳으로나 옮길 수 있으므로

가장 긴 증가수열의 길이를 구하고 n에서 빼면 최소 횟수를 구할 수 있고

 

7570번 문제의 경우엔 맨앞이나 맨뒤로만 보낼 수 있으므로

연속된 수들 중 가장 긴 증가수열의 길이를 구하고 n에서 빼면 최소 횟수를 구할 수 있다.

 

연속된 수들 중 가장 긴 증가수열의 길이를 구하는 알고리즘을 어떻게 짜야하나 생각을 많이 

해봤는데 방법들이 전부 O(n^2)이였다. 하지만 7570문제는 O(n^2)으로는 해결할 수 없기 때문에

어떻게 해야할지 몰랐는데.

알고리즘을 완전 잘하시는 마이구미님의 코드를 보고 감탄하였다.

 

이 두 문제에 대해 너무나도 잘 정리한 마이구미님의 글을 다음에 다시 한번 읽어보자!

https://mygumi.tistory.com/276

백준 7570번 줄 세우기 :: 마이구미

2631

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] a = new int[n+1];
        int [] dp = new int[n+1];
        
        for(int i=1; i<=n; i++)
            a[i] = scan.nextInt();
        
        for(int i=1; i<=n; i++) {
            dp[i] = 1;
            for(int j=1; j<i; j++) {
                if(a[i] > a[j] && dp[i]<=dp[j]) {
                    dp[i] = dp[j]+1;
                }
            }
        }
        Arrays.sort(dp);
        System.out.println(n-dp[n]);
        
    }

7570

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] dp = new int[n+1];
        
        for(int i=0; i<n; i++) {
            int k = scan.nextInt();
            dp[k] = dp[k-1]+1;
        }
        
        Arrays.sort(dp);
        System.out.println(n-dp[n]);
    }