BOJ 20192 : 순서 섞기
2021. 5. 2. 20:58ㆍPS/Ad-hoc & Constructive
관찰이 조금 까다로운 문제이다.
먼저 문제를 관찰하면
수열을 증감 상태로 나타내면 전환되는 점이 있는데, 이를 순서를 바꿀때 전환되는 점이 한번 섞을때 최대 그 반만큼 감소한다는 거다.
그래서 전환점을 O(N)에 찾으면 된다. 바꾼 횟수는 log2(전환점)으로 계산하면 된다.
'PS > Ad-hoc & Constructive' 카테고리의 다른 글
BOJ 12935 : 트리와 경로의 길이 2 (0) | 2021.11.16 |
---|---|
BOJ 1201 : NMK (0) | 2021.11.16 |
BOJ 15311 : 약 팔기 (0) | 2021.08.04 |
BOJ 21061 : Beautiful Permutation (0) | 2021.08.03 |
BOJ 14864 : 줄서기 (0) | 2021.05.11 |