BOJ 2631 - 줄세우기

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

 

문제를 보고 좀 생각하다가 LIS를 이용하면 된다는 걸 깨달았으나, LIS를 푼지 너무 오래되어 LIS를 구현하지 못해 실패했었다.

LIS 알고리즘을 다시 보고와서 정답을 맞출수있었다. LIS 문제 몇개 풀어봐야겠다...

#include <bits/stdc++.h>
using namespace std;
int n;
int a[204];
int cnt[204];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    fill(cnt, cnt + 204, 1);
    // 초ㅣ장 lis를 구하고 전체길이 - lis 해주면 될듯
    int longgest = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i] && cnt[j] + 1 > cnt[i])
            {
                cnt[i] = cnt[j] + 1;
            }
        }
        longgest = max(longgest, cnt[i]);
    }

    cout << n - longgest << "\n";

    return 0;
}

/*
5
4 1 2 3 5
*/