한국에 첨단 기술을 보유한 회사가 하나 있다.

이 회사는 커다란 직사각형 모양의 창고를 두고 있다.

창고의 좌우상하 각 모서리를 편의상 왼쪽, 꼭대기, 오른쪽, 밑바닥이라고 일컫겠다.

창고는 크기가 모두 같은 정사각형 격자 구역으로 분할돼 있다.

창고의 가로줄은 꼭대기에서 밑바닥까지 정수 1, 2, ...의 순으로 번호가 매겨져 있으며,

세로줄 역시 왼쪽에서 오른쪽으로 1, 2, ...의 순으로 번호가 매겨져 있다.

창고에는 귀중한 기계 장비를 담은 컨테이너가 보관된다.

컨테이너들은 제각기 다른 번호가 부여된다.

(꼭 1부터 N까지 빠짐없이 번호가 매겨지는 것은 아님) 컨테이너 하나는 정확히 정사각형 칸 하나를 차지한다.

창고는 충분히 크기 때문에, 창고에 집어넣어야 하는 컨테이너 수는 창고의 가로줄 수보다 작고, 세로줄 수보다도 작다.

컨테이너를 창고 밖으로 꺼내는 일은 없으며, 이 문제에서는 새 컨테이너을 2차원적으로 창고 안으로 집어넣는 경우만 생각한다.

창고 입구는 맨 왼쪽 꼭대기이다.

그리고 창고에는 일꾼과 관리자가 있다.

일꾼은 컨테이너를 식별 번호로 찾을 수 있게 하기 위해, 왼쪽 꼭대기 주위에 있는 컨테이너들을 다음과 같은 방법으로 정렬한다.

이번에 집어넣어야 하는 컨테이너의 번호가 k라고 하자. 일꾼은 맨 윗줄부터 시작하여 아래로 내려간다.

각 줄을 왼쪽부터 가로로 훑으며 번호가 k보다 큰 컨테이너를 찾는다. 그런 게 없으면 k번 컨테이너는 그 줄 맨 오른쪽에 쌓아둔다.

반면, k보다 번호가 큰 l이라는 컨테이너가 발견되면 l이 있던 곳에 k를 두고, l은 그 다음 줄로 밀려나,

지금까지 했던 방법을 거기서부터 반복하여 다른 곳에 놓이게 된다. (아랫줄에는 l 때문에 밀려나는 컨테이너가 또 생기고 그런 식으로 반복됨.)

그리고, 컨테이너가 하나도 없는 맨 아랫줄에 도달하면, 일꾼은 이 컨테이너를 그 줄 맨 왼쪽에 놓아둔다.

번호가 3, 4, 9, 2, 5, 1인 컨테이너가 차례대로 들어왔다면 창고에 컨테이너들이 들어가 있는 모습은 다음과 같게 된다.

관리자가 일꾼에게 와서 이런 이야기를 나눈다.

"5번 컨테이너는 4번보다 먼저 왔는가?" "아닙니다. 그건 있을 수 없어요." "컨테이너가 쌓인 모양만 보고 이것들이 도착한 정확한 순서를 알 수 있는가 보군." "꼭 그런 건 아니죠. 지금 쌓여 있는 컨테이너들은 3, 2, 1, 4, 9, 5와 같은 순서로 왔을 수도 있고,

3, 2, 1, 9, 4, 5일 수도 있고... 아무튼 있을 수 있는 열네 가지 경우 중 한 가지 순서대로 왔을 겁니다."

더 말하다가는 자신의 무식함만 더 드러낼 것 같아서 관리자는 그냥 가 버린다.

자, 여러분은 이 관리자를 도와야 한다.

컨테이너가 창고에 놓여 있는 모양을 입력받아서 이들이 어떤 순서대로 도착했을지 가능한 경우가 몇 가지인지 추정하는 프로그램을 작성하라.

(컨테이너가 3, 4, 9, 2, 5, 1의 순으로 왔을 때만 1 4 5: 2 9: 3과 같은 모양이 생기는 게 아니기 때문이다.

그리고 창고의 가로 세로 크기는 무한하다고 생각할 것.)

#1496 upload 11 done 8 how_to_reg 2

컨테이너(Depot) timer 641s memory - MB

#1496

컨테이너(Depot) 641s - MB