반응형
https://www.acmicpc.net/problem/7570
7570번: 줄 세우기
입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하
www.acmicpc.net
[ 문제풀이 ]
1. 어린이가 항상 맨 뒤나 맨 앞으로 가야 하므로 일반적인 증가하는 부분 수열이 아닌 연속으로 증가하는 최장 부분 수열을 찾아야 합니다. ex) 2, 4, 7 (x) 3, 4, 5 (o)
2. 겹치는 수가 없기 때문에 cnt 배열을 통해 각각의 수가 몇번 째 증가하는 수인지를 저장합니다.
3. cnt[ i ] = cnt[ arr[ i ] - 1 ]+1의 점화식을 활용하여 값을 저장해 줍니다.
4. ans = max(ans, cnt[ i ])를 통해 최장 연속 증가 부분 수열의 길이를 저장합니다.
5. N - ans를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include<iostream> using namespace std; int N; int arr[1000000]; int cnt[1000001]; int ans; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &arr[i]); } for (int i = 0; i < N; i++) { cnt[arr[i]] = cnt[arr[i] - 1] + 1; ans = max(ans, cnt[arr[i]]); } printf("%d", N - ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14621번 - 나만 안되는 연애 (C++) (0) | 2023.02.16 |
|---|---|
| [ 백준 ] 1937번 - 욕심쟁이 판다 (C++) (0) | 2023.02.15 |
| [ 백준 ] 11085번 - 군사 이동 (C++) (0) | 2023.02.13 |
| [ 백준 ] 2565번 - 전깃줄 (C++) (0) | 2023.02.12 |
| [ 백준 ] 17836번 - 공주님을 구해라! (C++) (0) | 2023.02.11 |