ACM ( 유명한 컴퓨터 제조사 ) 회사는 아래 그림과 같이 생긴 빌딩의 한 층을 빌렸다..
이 층은 복도를 따라 남과 북으로 200 개의 방이 있다. 최근 이 회사는 시스템을 재 정비를 할려는 계획을 세웠다. 이 계획은 방사이에 많은 테이블을 옮겨야 하는 것을 포함하고 있다. 복도는 좁고 테이블이 커서 단지 하나의 테이블만 이 복도를 지날 수 있다.
이 작업을 하기위한 효율적인 계획이 필요하다.
매니저는 방에서 다른 방으로 테이블을 옮기는 데 소요되는 시간이 10 분 안이라는 것을 알았다. i 번째 방에서 j 번째 방으로 테이블을 옮길 때 i 번 방 앞의 복도와 j 번 방 앞의 복도가 사용된다. 그래서 , 매 10 분 동안 복도가 중첩되어 사용되지 않는다면 여러개의 작업을 동시에 할 수 있다.
아래 테이블은 가능한 경우 , 불가능한 경우의 예이다.
태이블 이동 | 이유 | |
가능 | 30 번에서 50 번 방 과 60 번에서 90 번 방 | 복도를 공유하지 않음 |
11 번에서 12 번 방 과 14 번에서 13 번 방 | 복도를 공유하지 않음 | |
불가능 | 20 번에서 40 번 방 과 31 번에서 80 번 방 | 31 번에서 40 번 방 앞 복도 공유 |
1 번에서 4 번 방 과 3 번에서 6 번 방 | 3 번 방 앞 복도 공유 | |
2 번에서 8 번 방 과 7 번에서 10 번 방 | 7 번 방 앞 복도 공유 |
각 방에서 많아야 하나의 테이블이 들어가거나 나갈 것이다. 매니저는 모든 테이블을 옮기는 데 필요한 최소 시간을 구하는 방법을 찾고자 한다.
같은 방에서 같은 방으로 이동할 때도 복도를 사용하여야 한다.
입력 4 10 20 30 40 50 60 70 80 출력 10 입력 2 1 3 2 200 출력 20 입력 3 10 100 20 80 30 50 출력 30 입력 3 1 1 2 2 3 3 출력 20
출처:Taejon 2001