[BOJ] 5000. 빵 정렬

starbow·2024년 7월 2일

PS/CP

목록 보기

15/25

빵 $N$ 개의 현재 순서와 목표 순서가 주어집니다. 저희는 인접한 빵 3개를 골라 가장 오른쪽에 있는 빵은 가장 왼쪽으로, 나머지 빵은 오른쪽으로 한칸씩 이동하는 기술을 사용할 수 있고 이 기술만을 사용해서 목표 순서를 만들 수 있는지 판단해야 합니다.

먼저 현재 순서를 목표 순서로 변환하는 것을 하나의 permutation으로 볼 수 있습니다. (해당 permutation을 $p$ 라고 하겠습니다.)
그리고 우리가 사용할 수 있는 기술 또한 하나의 permutation으로 볼 수 있는데 even permutation이라는 특징이 있습니다. 이 특징을 활용하기 위해 permutation의 parity를 기준으로 케이스를 나눠서 살펴봅시다.

Case 1) $p$ 가 odd permutation일 때

당연하지만 목표 순서를 만들기 위해서는 $p$ 를 기술의 합성으로 표현할 수 있어야 합니다. 그리고 기술은 even permutation이므로 이것들을 합성한 permutation 또한 even permutation입니다. 즉, $p$ 가 odd permutation이라면 기술들의 합성으로 표현하는 것이 불가능 하고 다시 말해 목표 순서를 만들 수 없습니다.

Case 2) $p$ 가 even permutation일 때

먼저 다음 Theorem을 증명해 보겠습니다.

Theorem. 두 transposition을 합성한 permutation은 기술들의 합성으로 표현할 수 있다.

proof) permutation $(a \, b)(c \, d)$ 가 있다고 합시다. $(a < b, c < d)$
먼저 임의의 transposition $(x \, y)$ 는 다음을 만족합니다.

(x \, y) = (x \, x+1) \cdots (y-2 \, y-1)(y-1 \, y) \cdots (x+1 \, x+2)(x \, x+1)

참고로 $i, i+1, i+2$ 를 $i+2, i, i+1$ 로 바꾸는 변환은 $(i \, i+1)(i+1 \, i+2)$ 와, $i, i+1, i+2$ 를 $i+1, i+2, i$ 로 바꾸는 변환은 $(i+1 \, i+2)(i \, i+1)$ 와 같습니다. 즉, 다음이 성립합니다.

(x \, y) = (x \, x+1) \circ skill_1 \circ \cdots \circ skill_l \; \text{or} \; (x \, y) = skill_1 \circ \cdots \circ skill_{l'} \circ (x \, x+1)

위 내용을 토대로 $(a \, b)(c \, d)$ 를 다음과 같이 변환할 수 있습니다.

\begin{aligned} (a \, b)(c \, d) &= skill_{a_1} \circ \cdots \circ skill_{a_l} \circ (a \, a+1)(c \, c+1) \circ skill_{b_1} \circ \cdots \circ skill_{b_{l'}} \\ &= \begin{cases} skill_{a_1} \circ \cdots \circ skill_{a_l} \circ (a \, a+1)(a+1 \, a+2)(a+1 \, a+2)(a+2 \, a+3) \cdots (c \, c+1) \circ skill_{b_1} \circ \cdots \circ skill_{b_{l'}}, \quad \text{if} \;\, a \leq c \\ skill_{a_1} \circ \cdots \circ skill_{a_l} \circ (a \, a+1)(a-1 \, a)(a-1 \, a)(a-2 \, a-1) \cdots (c \, c+1) \circ skill_{b_1} \circ \cdots \circ skill_{b_{l'}}, \quad \text{if} \;\, a > c \end{cases} \\ &= skill_{a_1} \circ \cdots \circ skill_{a_l} \circ skill_{c_1} \circ \cdots \circ skill_{c_{l''}} \circ skill_{b_1} \circ \cdots \circ skill_{b_{l'}} \end{aligned}

즉, $(a \, b)(c \, d)$ 를 기술들의 합성으로 표현할 수 있습니다. 증명이 완료되었습니다.

$p$ 는 even permutation이므로 짝수개의 transposition의 합성으로 표현할 수 있습니다. Theorem에 의하여 두개씩 묶어서 기술들의 합성으로 바꾸면 $p$ 는 결국 기술들의 합성으로 표현할 수 있습니다. 즉, $p$ 가 even permutation이면 항상 목표 순서를 만들 수 있습니다.