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

 

 

오늘 열받는 일이 있어서 문제에 집중을 못했다...

그래도 오늘이 마지막이니까 ㅎㅎ

내일부터는 다시 자유다...

 

힘들게 일했더니 너무 피곤해서 이 문제는 다음에 다시 봐야겠다...

 

 

문제 2631번

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

 

 

다이나믹 프로그래밍
배치하는 문제를 만나면 가장 중요한 포인트는 기준을 잡기 -> 오름차순으로 정렬하라고 했으니 오름차순으로 가장 길게 정렬된 부분을 기준

LIS(최장 부분 증가수열): 앞에서부터 뒤로, 각각의 값이 이전 값보다 크고 가장 긴 부분 수열을 뜻함

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N = 0, result = 0;
	scanf("%d", &N);

	int child[201], dp[201];
	for (int i = 1; i <= N; i++) {
		scanf("%d", &child[i]);
	}

	for (int i = 1; i <= N; i++) {	// LIS
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (child[j] < child[i] && dp[i] <= dp[j]) {
				dp[i] += 1;
			}
		}
		result = max(result, dp[i]);
	}
	printf("%d", N - result);

	return 0;
}