KOI(한국정보올림피아드) 2001년 중등부 2번 줄세우기

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

#include <cstdio> #include <algorithm> using namespace std; #define MAX_N 200 int N; int input[MAX_N], D[MAX_N]; void solve() { D[0] = 1; //base case int v = D[0]; for(int i=0; i<N; i++) { D[i] = 1; for(int j=0; j<i; j++) { if(input[j] < input[i]) //증가하는 수열이라면 D[i] = max(D[i], D[j]+1); } v = max(v, D[i]); } printf("%d", N-v); //옮겨지는 아이들의 최소 수를 출력하기 위해 전체 학생수에서 가장 긴 부분수열을 빼줌. } int main() //LIS알고리즘 { scanf("%d", &N); for(int i=0; i<N; i++) { scanf("%d", &input[i]); } solve(); return 0; }