[BAEKJOON] 2631 줄세우기

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int>map(201), DP(201, 0); int n; scanf("%d", &n); for (int j = 0; j < n; j++) scanf("%d", &map[j]); int Max; for (int j = 0; j < n; j++) { Max = 0; for (int k = 0; k < j; k++) { if (map[j] > map[k]) Max = max(DP[k], Max); } DP[j] = Max + 1; } int answer = 0; for (int j = 0; j < n; j++) answer = max(answer, DP[j]); printf("%d", n - answer); return 0; }

가장 큰 증가하는 부분 수열을 찾은 다음

그 사이에 남은 숫자를 넣으면 된다

순열 조합!