https://www.acmicpc.net/problem/7570
7570번: 줄 세우기
입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하
www.acmicpc.net
[난이도] Gold4
[유형] DP
[풀이]
값이 1씩 증가하는 LIS를 구한다. 이 LIS에 포함되지 않은 숫자들은
모두 앞 또는 뒤로 옮겨줘야 정렬을 할 수 있기 때문에 N-(LIS의 길이) 가 정답이다.
#include <algorithm> #include <cstdio> using namespace std; int N,dp[1000001],v,ans; int main(){ scanf("%d",&N); for(int i=1;i<=N;i++){ scanf("%d",&v); dp[v] = dp[v-1]+1; ans = max(ans,dp[v]); } printf("%d",N-ans); }
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/7570.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold4] 11562 : 백양로 브레이크 (C++) (0) | 2020.12.30 |
|---|---|
| [BOJ/백준][Gold4] 10993 : 별 찍기 - 18 (C++) (0) | 2020.12.30 |
| [BOJ/백준][Gold4] 11780 : 플로이드2 (C++) (0) | 2020.12.27 |
| [BOJ/백준][Gold4] 2157 : 여행 (C++) (0) | 2020.12.27 |
| [BOJ/백준][Gold4] 2306 : 유전자 (C++) (0) | 2020.12.27 |