BOJ 5000 - 빵 정렬 (Python3)

난 세그먼트 트리를 모른다. 그런데 어느 날 balbad.ac solved.ac의 태그를 보다 보니 내가 세그먼트 트리 태그가 달린 문제를 푼 게 아닌가. 그것도 두 문제나. 이것은 기여가 잘못되었거나 아니면 비슷한 난이도의 다른 풀이가 있거나 둘 중 하나.

아니나 다를까 세그먼트 트리를 전혀 쓰지 않는 풀이법이 있었다. 대신 일정 이상의 수학 지식과 직관력이 요구되는 문제였다. 젠장 또 수학 문제야. 나는 수학 문제를 보고 말았어. 이제 나는 수학 문제를 풀어야만 해... 아무튼.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

상근이는 빵집에서 일한다. 상근이의 퇴근하기 전에 하는 마지막 업무는 빵을 사장이 원하는 순서대로 정렬하는 것이다.

최근에 상근이는 선영이에게 신기한 기술을 하나 배웠다. 이제 상근이는 기술을 이용해 서로 인접해 있는 빵 세 개를 동시에 주걱으로 던질 수 있다. 놀라운 점은 빵이 땅으로 내려올 때는 가장 오른쪽에 있던 빵이 가장 왼쪽으로 가고, 나머지 빵은 한 칸씩 오른쪽으로 이동하게 된다는 점이다. 즉, 빵의 순서가 $[1,2,3,4]$일 때, $[2,3,4]$를 주걱을 이용해서 던지면, 빵이 땅에 내려온 후의 순서는 $[1,4,2,3]$이 되는 것이다.

이제 상근이가 퇴근할 시간이다. 상근이의 앞에는 지금 빵이 놓여져 있다. 지금 놓여져있는 빵의 순서와 사장이 원하는 순서가 주어졌을 때, 선영이에게 배운 기술만을 사용해서 빵을 정렬할 수 있는지 없는지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 빵의 개수 $n$ $(3\le n\le 100000)$이 주어진다. 둘째 줄에는 빵의 현재 순서가 주어지고, 셋째 줄에는 사장이 원하는 빵의 순서가 주어진다. 빵은 1부터 n까지 숫자로 나타낼 수 있다. 두 빵의 번호가 같은 경우는 없다.

 

예제 입력)

# 예제 입력 1
4
1 3 4 2
4 3 2 1

# 예제 입력 2
6
1 2 3 4 5 6
6 5 4 3 2 1

 

출력

만약, 상근이가 선영이에게 배운 기술만을 사용해서 사장이 원하는 순서를 만들 수 있으면 "Possible"을, 불가능하면 "Impossible"을 출력한다.

 

예제 출력)

# 예제 출력 1
Possible

# 예제 출력 2
Impossible

 

---

내 코드

def cyc_decomp(arr):
    n = len(arr)
    check = [False]*n
    ans = []
    for i in range(n):
        if not check[i]:
            ix = arr[i]; tmp = [i]; check[i] = True
            while ix != i:
                tmp.append(ix); check[ix] = True; ix = arr[ix]
            ans.append(tmp)
    return ans
N,arr1,arr2 = int(input()),[0],[0]
arr1.extend(list(map(int,input().split())))
arr2.extend(list(map(int,input().split())))
ans1,ans2 = cyc_decomp(arr1),cyc_decomp(arr2)
parity1,parity2 = 1,1
for i in ans1: parity1 *= pow(-1,len(i)+1)
for i in ans2: parity2 *= pow(-1,len(i)+1)
print(f'{"P" if parity1==parity2 else "Imp"}ossible')

 

일단 symmetric group $S_n$에 대한 지식이 필요하다. Cycle notation이 무엇을 의미하는지 정도는 기본 지식으로 가지고 있다고 가정하고 풀이를 쓰겠다. 모르는 사람은 이 문서를 읽고 오라.

여기서 $i,i+1,i+2$번째에 위치한 빵 세 개에 기술을 쓴다는 것은 주어진 순열에 $\tau =(i,i+2,i+1)$을 곱한다, 정확하게는 주어진 순열 $\sigma$를 $\tau \sigma$로 변환한다는 뜻이다. 그러면 적당한 기술을 사용해서 $\sigma$를 $\rho$로 변환할 수 있냐는 문제는 ${\tau }_1{\tau }_2\cdots {\tau }_k=\sigma {\rho }^{-1}$인 3-cycle ${\tau }_i$들이 존재하냐는 문제가 된다.

그리고 alternative group $A_n$은 3-cycle로 생성되므로(증명은 S. Lang의 Algebra 32페이지를 참조하라) $\sigma {\rho }^{-1}\in A_n$이기만 하면 풀린다. 만세!

 

로 증명이 됐으면 내가 이 풀이를 굳이 블로그로 썼겠는가. 위 풀이는 결론만 맞고 과정이 살짝 엉망이다.

모든 3-cycle $\tau$기 $A_n$의 원소임은 맞다. 그리고 $A_n$이 group이므로 $\sigma$가 '기술'로 인하여 $\rho$로 변형이 가능하면 $\sigma {\rho }^{-1}$도 $A_n$의 원소임은 맞다. 하지만 $A_n$이 $(i,i+2,i+1)$로만 생성된다는 보장이 과연 있나? 아직까지는 없다. 증명 없이 무작정 풀디가 틀리면 어쩌려고...

하지만 위에서 말한 바 있듯이, 확실히 결론은 맞다. 왜 그러는지 증명해 보자.

 

모든 원소가 다른 수열 $a=[a_1,a_2,\cdots ,a_n]$이 모든 원소가 다른 수열 $x=[x_1,x_2,\cdots ,x_n]$의 재배열이면서 $a_1<a_2<\cdots <a_{n-2}$이며 $a_{n-2}<a_{n-1},a_n$일 시, 곧 마지막 두 개의 항만을 제외하고 수열이 정렬되었을 시 $a$를 $x$의 유사 정렬이라고 정의하자. 

그러면 '기술', 즉 ${\tau }_i=(i,i+2,i+1)$인 ${\tau }_1,\cdots ,{\tau }_{n-2}$들 전체 혹은 일부만을 왼쪽에 곱하면서 수열을 유사 정렬할 수 있다(중명은 후술한다). 게다가 그렇게 되면 $\sigma$와 $\sigma$의 유사 정렬인 ${\sigma }_{ϵ}$는 sign이 같다. 곧 $\sigma {\sigma }_{ϵ}^{-1}$은 항상 $A_n$의 원소이다.

심지어 $S_n$의 원소 $\sigma$의 유사 정렬인 ${\sigma }_{ϵ}$은 둘 중 하나다. $\sigma \in A_n$이면 ${\sigma }_{ϵ}=[1,2,\cdots ,n]$이고 그렇지 않다면 $[1,2,\cdots ,n-2,n,n-1]$이다. 그러므로 $\sigma ={\tau }_{x_1}\cdots {\tau }_{x_r}{\sigma }_{ϵ}$이며 $\rho ={\tau }_{y_1}\cdots {\tau }_{y_s}{\rho }_{ϵ}$일 때, $\sigma$와 $\rho$의 sign만 같다면 ${\sigma }_{ϵ}={\rho }_{ϵ}$이 되며, $\rho ={\tau }_{z_1}\cdots {\tau }_{z_k}\sigma$인 $z_1,\cdots ,z_k$이 존재한다. 왜냐하면 ${\tau }_i^{-1}={\tau }_i^2$이기 때문이다.

 

이제 유사 정렬의 가능성에 대해서 증명해 보자. 우선 $n=3$일 때는 자명하다. $[a,b,c]$에 기술을 쓰면 $[c,a,b],[b,c,a]$를 얻을 수 있는데, 이렇게 $a,b,c$ 중 가장 작은 것을 맨 앞으로 땡기면 되게 때문이다.

이제 $n=N-1$일 때 유사 정렬이 가능하다고 하자. 그러면 수열 $a=[a_1,\cdots ,a_N]$을, 첫 번째 항만 빼고 유사 정렬을 할 수 있다. 길이 $N-1$인 수열은 귀납적 정의에 의해서 유사 정렬이 가능하다고 이미 했다. 그 결과물을 $[a_1,b_2,b_3,\cdots ,b_N]$이라고 하자.

그러면 $a_1<b_2$일 때는 이미 유사 정렬이 완료된 것이고, 그렇지 않을 경우 ${\tau }_1^2$을 사용해서 $p=[b_2,b_3,a_1,b_4,\cdots ,b_N]$으로 변환시킬 수 있다. 여기서 $b_2$가 minimal element이므로, $p$를 첫 번째 항만 빼놓고 유사 정렬을 시킨 $[b_2,c_2,c_3,\cdots ,c_N]$은 수열 $a$의 유사 정렬이 된다.

따라서 귀납법에 의해서, 3 이상의 임의 길이의 수열은 '기술'로 유사 정렬을 시킬 수 있다.

이제 위 결과와 종합하면, 두 수열의 sign이 같으면 가능하며 다르면 불가능하다는 결과를 얻을 수 있다. 수열의 sign은 순열 사이클 분할을 한 뒤 각 사이클 길이 $l$에 대해서 $(-1{)}^{l-1}$을 곱하는 방식으로 체크 가능하다.

 

이로서 5000번의 풀이를 마친다.