[BAEKJOON] 7570 줄 세우기 (C++)

문제 링크

https://www.acmicpc.net/problem/7570

7570번: 줄 세우기

 

문제

1~N까지의 숫자 N개가 임의의 순서로 주어진다.

ex) N = 5 -> 1 3 2 4 5

 

이 숫자를 크기 순서로 재배치하려고 하는데, 수행할 수 있는 처리는 3가지이다.

1. 가만히 둔다.

2. 맨 뒤로 이동시킨다.

3. 맨 앞으로 이동시킨다.

 

재배치하는데 드는 최소 연산 횟수를 계산하는 문제 (가만히 두는 경우는 연산에 포함 X)

 

풀이

N=1000000 이므로 N^2보다 더 빠른 풀이가 필요하다.

처음 접근은 한 숫자를 봤을 때 해당 수가 뒤로 가는지 이득인지 앞으로 가는 게 이득인지를 판단할 수 있는지 고민했다.

하지만 숫자가 이동함에 따라 뒤에 있는 수들은 다른 조건에서 판단하게 된다. 앞에 발생한 경우에 대해서 뒤의 사건들이 영향을 받으므로 최선의 선택이 무엇인지 보장할 수 없다고 생각했다.

 

문제의 핵심은 얼마나 많은 수를 이동시키는지를 구하는 것이다.

즉, 어떤 과정으로 줄이 세워지는지는 고민할 필요가 없다.

 

이동할 필요가 없는 수들의 개수를 구하고 이를 N에서 빼준다면, 이동해야하는 수의 개수를 구할 수 있다.

이동할 필요가 없는 수 = 이미 줄이 세워져 있는 수

 

Longest Increasing number 와 비슷한 맥락에서 자기 자신 이전에 있는 수들 중 증가하는 수들의 최대 길이를 구한다.

이 때 증가 폭이 1이어야 한다는 특징이 추가된다.

 

 for (int i = 0; i < N; i++) {
        cin >> num;
        I[num] = I[num - 1] + 1;
        maxLen = max(I[num], maxLen);
    }

만약 i번째에 있는 수 k를 확인한다고 가정하자.

i-1번째까지 확인했을 때 I[k-1] = a 의 의미는 k-1까지 순차적으로 증가하는 수의 길이가 a개라는 것이다.

즉 (k-1-a) , (k-a), (k-a+1) .... (k-1)이 i-1번째까지 순서를 유지하며 존재한다.

 

따라서 I[k] = I[k-1] + 1 이 된다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;

int N;
int I[1010101];
void Solve() {
    cin >> N;
    int num, maxLen=0;
    for (int i = 0; i < N; i++) {
        cin >> num;
        I[num] = I[num - 1] + 1;
        maxLen = max(I[num], maxLen);
    }

    cout << N - maxLen;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}