백준 2631 C++

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

2631번: 줄세우기

 

문제 정리

주어진 아이들의 키를 가장 적게 움직여서 증가수열이 되도록 정렬하는 문제

문제가 왤케 쓸데없이 길어;;; 난독 오게 생ㄱ김

 

생각

DP로 푸는데 아이의 위치를 변경할 때마다 그 때까지의 최대 증가수열의 길이를 저장

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;

    int children[N];
    int dp[N];

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

    fill(dp, dp + N, 1);

    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (children[j] < children[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
                //현재 아이(i)의 키가 앞쪽 아이들의 키보다 크다면 현재 아이를 이전 아이들의 증가수열에 추가
            }
        }
    }

    int result = N - *max_element(dp, dp + N);
    cout << result << endl;
}

 

점화식

dp[i] = max(dp[i], dp[j] + 1)

 

중요한 점

각 아이들이 최소한 자기 자신만으로도 증가수열이 된다라는 조건 -> 1부터 시작하라는 소리

    fill(dp, dp + N, 1);

이걸로 배열을 1로 초기화해서 아이들이 자기 자신만으로도 길이가 1인 증가수열을 만들게 함!

 

알게된 점

*max_element(dp, dp + N)

얘는 배열 dp에서 가장 큰 값을 가진 요소의 값을 반환함