Problems
BOJ 2301 마법 구슬

BOJ 2301 마법 구슬

문제 링크:

문제 내용

N=2kN = 2^k 길이의 순열 중에서 다음의 조건을 모두 충족하는 순열을 아무거나 하나 찾아 출력하세요.

  • 이 순열의 첫 번째 원소는 MM입니다.
  • 이 순열의 각 원소를 a1,a2,⋯ ,aNa_1, a_2, \cdots, a_N이라고 할 때, ∣a2−a1∣,∣a3−a2∣,⋯ ,∣aN−aN−1∣|a_2 - a_1|, |a_3 - a_2|, \cdots, |a_N - a_{N-1}| 또한 순열입니다. 즉, 이웃한 원소의 차이는 1,2,3,⋯ ,N−11, 2, 3, \cdots, N-1 중 하나이며 중복되지 않습니다.

문제 풀이

스포일러

NN이 2의 거듭제곱이므로, N2\frac{N}{2} 크기에 대한 답을 이용해 NN 크기의 답을 구성하는 방법을 생각합니다.

N2\frac{N}{2} 크기의 답에는 이웃의 차이가 1,2,⋯ ,N2−11, 2, \cdots, \frac{N}{2} - 1이 등장합니다. 모든 차이를 N2\frac{N}{2}만큼 늘리려면, 그 답에서 N4\frac{N}{4} 이하인 값과 초과인 값이 번갈아 나온다면 큰 값들에 모두 N2\frac{N}{2}를 더하면 가능합니다. 그 다음 두 개의 수열을 N2\frac{N}{2} 차이로 연결해주면 크기 NN의 답이 됩니다.

N=2N=2와 N=4N=4에서 모든 시작점에 대해 시도해보면 이 조건을 충족하는 답이 존재하므로, 이를 활용하여 다음과 같은 답을 구성할 수 있습니다.

  • NN의 값들을 N4\frac{N}{4} 초과 3N4\frac{3N}{4} 이하인 것과 아닌 것으로 분류합니다.
  • MM이 속하는 집합에서 MM이 M′M'번째 수라면, N2\frac{N}{2} 길이의 M′M'으로 시작하는 답을 재귀적으로 구합니다.
  • 그 답의 값들을 적절히 옮긴 다음, N2\frac{N}{2} 크기의 점프를 하여 반대쪽 집합의 시작점 M′′M''을 구합니다.
  • 다시 N2\frac{N}{2} 길이의 M′′M''으로 시작하는 답을 재귀적으로 구하여 답을 완성합니다.

이렇게 완성된 수열 역시 추가 조건을 충족함을 어렵지 않게 보일 수 있습니다.

Last updated on
BOJ 22757 HillsBOJ 23091 Calculate! 3