17505번

【백준】- 20921. 그렇고 그런 사이

문제 https://www.acmicpc.net/problem/20921 20921번: 그렇고 그런 사이 정수 $N$, $K$가 주어진다. ($2 \leq N \leq 4\,242$, $0 \leq K \leq \frac{N(N-1)}{2}$) www.acmicpc.net 풀이 $N$ 이 최대 $4\;242$ 이기 때문에, $O(N^2)$ 와 $O(N)$ 의 시간복잡도의 풀이 모두 사용할 수 있습니다. 저는 두 방법 모두 설명해 보고자 합니다. 여러분은 어느 방식으로 푸셨나요? $O(N^2)$ 풀이 인접한 번호를 서로 교환해 보기 여기 사람들의 번호가 일렬로 나열되어 있습니다. 이 상태에서, 두 인접한 번호(오른쪽 번호가 더 큰)를 골라 서로의 위치를 바꾸었다고 가정해 볼게요. 과연 그렇고 그런 사이의 ..