728x90
오늘 열받는 일이 있어서 문제에 집중을 못했다...
그래도 오늘이 마지막이니까 ㅎㅎ
내일부터는 다시 자유다...
힘들게 일했더니 너무 피곤해서 이 문제는 다음에 다시 봐야겠다...
문제 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;
}
728x90
'백준 > C++' 카테고리의 다른 글
[C++] 백준 11650번 - 좌표 정렬하기 (0) | 2024.05.06 |
---|---|
[C++] 백준 10824번 - 네 수 (0) | 2024.05.05 |
[C++] 백준 2792번 - 보석 상자 (0) | 2024.05.02 |
[C++] 백준 10867번 - 중복 빼고 정렬하기 (1) | 2024.05.01 |
[C++] 백준 6236번 - 용돈 관리 (0) | 2024.04.30 |