[백준 2631번] 줄세우기 (C++)

문제링크 : https://www.acmicpc.net/problem/2631

2631번: 줄세우기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, result=0;
int arr[201];
int dp[201]; // LIS 이용

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    for(int i=0; i<N; i++)
    {
        dp[i]=1; //최소 길이 1
        for(int j=0; j<i; j++) //현재 값과 그 이전 값들을 비교
        {
            if(arr[j]<arr[i] && dp[i] < dp[j]+1) dp[i]++;
        }
        result = max(result, dp[i]); //가장 긴 길이 (움직이지 않는 고정 값들) 저장
    }

    cout << N-result; //움직이는 값들만 추려내기

    
}

LIS(최장 증가 수열)을 이용한 DP 문제이다.

LIS 부분 만큼이 움직일 필요가 없는 고정 값들이고, 나머지 값들은 움직여야 한다는 것을 이용한다.

 

해당 문제에서 예제에 따른 LIS는 {3, 5, 6]이다.

줄을 증가하는 순서대로 세워야 하기 때문에 이미 증가하는 줄을 이루는 {3, 5, 6}은 건들일 필요가 없다.

따라서 {3, 5, 6}을 제외한 나머지 숫자들을 움직이면 되기에 전체 길이인 N에서 LIS의 길이를 뺀 값을 출력하면 된다.