벽장문의 이동 |
---|
N개의 같은 크기의 벽장들이 일렬로 붙어져 있고 벽장의 문은 N-2개만이 있다. 한 벽장 앞에 잇는 문은 이웃 벽장 앞에 문이 없다면(즉, 벽장이 열려 있다면) 그 벽장 앞으로 움직일 수 있다. 그림은 7개의 벽장의 예이다. 그림에서 2번 벽장과 5번 벼강이 열려 있고, 나머지 벽장은 닫혀 있다. 벽장 문은 좌우 어느 쪽이든 그 이웃 벽장이 열려 있다면 그 쪽으로 한 칸씩 이동할 수 있다. 그림에서 주어진 상태에서는 1번 벽장을 닫고 있는 벽장문을 오른쪽으로 한 칸 이동함으로써 1번 벽장을 사용할 수 있다. 이 때 2번 벽장은 닫혀져 사용할 수 없다. 역시 5번 벽장이 열려 있으므로 4번 벽장 또는 6번 벽장 앞의 벽장문을 5번 벽장 앞으로 이동시킬 수 있다. 풀어야 할 문제는 입력으로 주어지는 사용할 벽장의 순서에 따라서 벽장문을 이동하는 순서를 찾는 것이다. 이 때 벽장문의 이동 횟수를 최소로 하여야 한다. 입력은 다음과 같이 주어지며, 열려있는 벽장의 갯수는 항상 2개이다. 예를 들어, 사용할 벽장 순서가 3 1 6 5 이면, 3번 앞의 문을 2번으로 옮겨서 3번 벽장을 사용하고(문 이동횟수=1), 다음에 1번과 2번 앞에 있는 문을 오른쪽으로 하나씩 옮겨서(문 이동횟수=2) 1번벽장을 사용하며, 6번 앞에 있는 문을 왼쪽으로 옮겨서 6번 벽장을 사용하고(문 이동횟수=1), 다시 그 문을 오른쪽으로 옮겨서 5번 벽장을 사용한다(문 이동횟수=1). 따라서 문이 이동한 횟수의 합은 5 이다. 또한 같은 벽장을 여러 번 사용할 수도 있다. |
입력 | |
---|---|
첫 번째 줄에 벽장의 갯수를 나타내는 2보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려 있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들의 순서의 길이(최대 20), 그리고 그 다음 줄부터 사용할 벽장의 번호가 한 줄에 하나씩 순서대로 주어진다. |
출력 | |
---|---|
첫 번째 줄에 벽장문의 최소 이동횟수를 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 7 25 4 3 1 6 5 | |
출력 | 5 |
출처 | |
---|---|
1997년 한국정보올림피아드 전국 본선 고등부 3번 문제 |