https://www.acmicpc.net/problem/17022
17022번: Sleepy Cow Sorting
The first line of input contains $N$. The second line contains $N$ space-separated integers: $p_1, p_2, p_3, \dots, p_N$, indicating the starting order of the cows.
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/364
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)
1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트
rudalsd.tistory.com
1. N - 1부터 1까지 for문을 통해 돌면서 arr[ i ] < arr[ i - 1 ] 일 때의 i를 pivot으로 설정합니다.
2. pivot 부터 N - 1까지는 오름차순으로 정렬되어 있으므로 0부터 pivot - 1 까지의 수만 옮겨주면 됩니다.
3. 0부터 pivot - 1까지 for문을 통해 돌면서 pivot ~ N 까지의 수 중 현재 수보다 작은 수들의 개수와 현재 수 ~ pivot 사이의 수들의 개수를 더하면 원하는 수를 얻을 수 있습니다.
4. pivot을 출력하고, 앞의 수들의 이동 횟수를 출력합니다.
[ 소스코드 ]
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include<iostream> using namespace std; int N; int arr[100000]; int segTree[200002]; int pivot; void updateTree(int idx) { while (idx != 0) { segTree[idx]++; idx >>= 1; } } int getTree(int l, int r) { int ret = 0; while (l <= r) { if (l & 1) { ret += segTree[l]; l++; } if (~r & 1) { ret += segTree[r]; r--; } l >>= 1; r >>= 1; } return ret; } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &arr[i]); } for (int i = N - 1; i > 0; i--) { if (arr[i] < arr[i - 1]) { pivot = i; break; } } for (int i = pivot; i < N; i++) { updateTree(N + arr[i] - 1); } printf("%d\n", pivot); for (int i = 0; i < pivot; i++) { printf("%d ", pivot - i - 1 + getTree(N, N + arr[i] - 1)); updateTree(N + arr[i] - 1); } } | cs |
'백준' 카테고리의 다른 글
| [ 백준 ] 12893번 - 적의 적 (C++) (0) | 2023.06.04 |
|---|---|
| [ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++) (0) | 2023.06.03 |
| [ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++) (0) | 2023.06.01 |
| [ 백준 ] 20955번 - 민서의 응급 수술 (C++) (0) | 2023.05.31 |
| [ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++) (0) | 2023.05.30 |