RSS Feed

최대 혼합 배치

Problem 336

출제 일시 : 2021-06-15 00:03:01

어떤 열차는 객차 4량을 ABCD 순서로 연결해 운송합니다. 가끔은 객차를 모아보면 올바른 순서가 아닐 때가 있습니다.
객차를 재배열 하기 위해서는 모든 객차를 대형 회전판위의 궤도로 옮깁니다. 특정 칸에서 객차를 분리한 뒤에 열차는 아직 연결돼 있는 객차를 회전판에서 끌어냅니다. 남은 객차들은 180도 회전시킵니다. 이제 모든 객차를 다시 결합시키고 이 과정을 회전판의 사용을 최소화하도록 필요한 만큼 반복합니다.
ADCB같은 배치는 쉽게 풀립니다: A와 D사이에서 객차를 분리하고, DCB를 회전시키면 올바른 순서를 얻을 수 있습니다

그러나 기관사 김단순씨는 효율적이지 않아서 처음에 객차 A를 제자리에 연결하고, 그 다음에 객차 B를 연결하고.. 항상 이렇게 문제를 해결합니다.

객차가 4량이라면, 김단순씨에게 최대 혼합 배치로 부르는 최악의 배치는, DACB와 DBAC입니다; 각각은 5회의 회전이 필요합니다(가장 효율적인 방법으로는 단 3회의 회전으로 풀립니다). 김단순씨가 DACB를 푸는 과정은 아래와 같습니다.

p336_maximix.gif

객차가 6량이라면 모두 24가지의 최대 혼합 배치가 있고 그중에서 사전 순서로 10번째 최대 혼합 배치는 DFAECB 입니다.

객차가 11량일 때, 사전 순서로 2011번째 최대 혼합 배치를 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.