[ABC006 D] トランプ挿入ソート

난이도: 1696 // 실험적

 

태그

• Longest Increasing Subsequence
• Imperfect Time Complexity (당시 정해는 \( O(N \log N) \)으로 추정)

 

번역

\( N \)개의 카드가 주어집니다. 각각의 카드에는 정수 하나가 쓰여있습니다.

 

나열된 카드에 아래 작업을 원하는 만큼 적용시킬 수 있습니다.

• 원하는 카드 한 장을 빼낸 뒤, 원하는 위치에 삽입한다.

 

카드에 적힌 수가 오름차순이 되도록 하기 위해 실행해야 하는 작업의 최소 횟수를 구하세요.

 

추가 조건

두 장 이상의 카드에 같은 수가 적혀있는 경우는 없습니다.

또한, 카드에 적힌 수는 \( 1 \) 이상 \( N \) 이하입니다.

즉, 카드에 적힌 숫자들을 나열하면, 순열이 완성됩니다.

 

풀이

1. 한 장의 카드에 작업을 여러 번 진행한다면?

사실 이럴 필요 없습니다.

카드에 추가적인 제약 조건도 없으니, 그냥 처음에 이동시킬 때 원하는 지점으로 이동시키면 되기 때문이죠.

 

2. 작업을 여러 번 진행한다면?

작업을 \( K \)번 진행한다면, \( K \)장의 카드를 빼낸 뒤 이를 원하는 위치에 삽입하는 형태가 됩니다.

이 카드들은 우리가 원하는대로 조종할 수 있으므로, 작업을 하지 않는 \( N-K \)장의 카드에 대해 생각해봅시다.

 

3. 작업이 진행되지 않는 카드들의 조건은?

작업이 진행되지 않는 카드들 간의 순서는 변경되지 않습니다.

그러니, 작업이 진행되지 않는 카드들끼리는 정렬되어있어야 하겠죠.

 

다르게 말하자면, 이 카드들은 오름차순이어야 합니다.

 

이 조건 외에는 추가적인 제약이 없습니다.

저 카드들만 오름차순이라면, 우리가 움직일 수 있는 카드들은 항상 적당한 위치에 끼워넣을 수 있기 때문이죠.

 

4. 이제 원래 문제로 돌아와보자.

\( K \)장의 카드를 움직인다는 것은, \( N-K \)장의 카드를 가만히 놓겠다는 의미이고,

이는 \( N-K \)장의 카드가 정렬되어있어야 유효합니다.

 

연산 횟수 = 움직이는 카드의 개수 = \( K \)를 최소화해야 하므로,

자연스럽게 \( N-K \)를 최대화해야 합니다.

 

길이가 최대인 오름차순을 만든다?

결국, 최대 증가 부분 수열을 찾아야 한다는 의미가 됩니다.

 

코드

시대가 좋아져서, \( O(N^2) \)이 시간 내에 통과를 하게 됩니다.

int arr[30020];
int dp[30020];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < i; j++){
            if (arr[j] < arr[i]){ dp[i] = max(dp[i], dp[j]+1); }
        }
    }
    int res = *max_element(dp, dp+n+1);
    cout << n-res;
}