BOJ 21061 : Beautiful Permutation
2021. 8. 3. 22:12ㆍPS/Ad-hoc & Constructive
https://www.acmicpc.net/problem/21061
21061번: Beautiful Permutation
A permutation $a_0, a_1, \ldots, a_{n - 1}$ of $0, 1, \ldots, n - 1$ is said to be beautiful if the sequence $b_0, \ldots, b_{n - 1}$ defined as $b_i = |a_i - i|$ is also a permutation of $0, \ldots, n - 1$. Given $n$, construct a beautiful permutation o
www.acmicpc.net
상당히 힘들었던 문제.
풀고 나서 보는 걸 추천한다.
일단 n%4의 값이 0,1일때만 성립하고, 아니면 NO다.
성립한다면 다음 방법으로 수열을 만들면 된다
-n서부터 시작해서 -n, +n-1, -(n-2), +n-3.....를 n/2까지 반복하고 n/2일때는 헤당 연산을 하지 않고, 2번째 단계가 끝난 후 시행한다.
-n/2-1서부터 시작해서 위 과정과 동일하게 1까지 반복한다.
-나머지 하나의 수가 남는데 그건 a[i]=b[i]의 경우이다. 그냥 출력해도 무방하다.
'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 14864 : 줄서기 (0) | 2021.05.11 |
| BOJ 20192 : 순서 섞기 (0) | 2021.05.02 |