LoCeL
[BOJ 7570] 줄 세우기 본문
가장 긴 증가하고 연속하는 부분 수열을 찾으면, N - (수열의 길이) 가 답이 된다.
가장 긴 증가하고 연속하는 부분 수열은, A[i] 앞에 A[i]-1이 있었는지를 간단히 판별하여 DP 테이블을 채울 수 있다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
int A[1000005], B[1000005], cnt[1000005];
int D[1000005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
B[A[i]] = i;
D[i] = 1;
}
for (int i = 1; i <= N; i++) {
cnt[A[i]]++;
if (cnt[A[i]-1]) D[i] = D[B[A[i]-1]] + 1;
}
int ans = 0;
for (int i = 1; i <= N; i++)
ans = max(ans, D[i]);
cout << N-ans;
return 0;
}
'PS' 카테고리의 다른 글
(06/20 ~ 06/26) 랜덤 골드 디펜스 (0) | 2022.06.25 |
---|---|
[BOJ 2759] 팬케익 뒤집기 (0) | 2021.06.27 |
[BOJ 12865] 평범한 배낭 (0) | 2020.08.13 |
[BOJ 11727] 2 x n 타일링 2 (0) | 2020.08.05 |
[BOJ 11724] 연결 요소의 개수 (0) | 2020.08.05 |
Comments