반응형
https://www.acmicpc.net/problem/2631
2631번: 줄세우기
KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기
www.acmicpc.net
[ 문제풀이 ]
1. LIS를 활용하여 최장 증가 수열의 개수를 구합니다.
2. 아이들의 수에서 LIS의 사이즈를 뺀 값을 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include<iostream> #include<vector> #include<algorithm> using namespace std; int N; int arr[200]; vector<int> lis; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &arr[i]); } lis.push_back(arr[0]); for (int i = 1; i < N; i++) { if (lis[lis.size() - 1] < arr[i]) { lis.push_back(arr[i]); } else { auto idx = lower_bound(lis.begin(), lis.end(), arr[i]); *idx = arr[i]; } } printf("%d", N - lis.size()); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2225번 - 합분해 (C++) (0) | 2022.10.21 |
|---|---|
| [ 백준 ] 2011번 - 암호코드 (C++) (0) | 2022.10.20 |
| [ 백준 ] 2636번 - 치즈 (C++) (0) | 2022.10.16 |
| [ 백준 ] 3954번 - Brainf**k 인터프리터 (C++) (0) | 2022.10.15 |
| [ 백준 ] 15486번 - 퇴사 2 (C++) (0) | 2022.10.14 |