열쇠 수리공(KRIZA) timer 1초 memory 64MB

경제 상황이 좋지 않아 많은 사람들이 일자리를 잃었다. 이러한 위기 상황에도 우리가 읽고 있는 이 문제의 주인공 준혁이는 일자리를 구했다. 한 대형 호텔의 보조 열쇠수리공으로 다음 주 월요일부터 출근할 예정이다. 이에 앞서 오늘 준혁이는 실기 테스트를 받는다.

아래 그림과 같이 여러 개의 열쇠가 달려있는 고리를 받아서 객실을 차례로 돌며 객실의 문을 열고 내부를 본 후에 다시 잠그는 일을 K번 해야 하는데 아래 제약 사항을 지켜야 한다.

<제약사항> - 객실을 방문할때는 방향을 바꾸거나 건너뛸 수 없다. 진행방향은 항상 오른쪽 이다. - 열쇠고리를 뒤집거나 열쇠를 찾을 때, 방향을 바꾸거나 건너뛰어 찾을 수 없다.   한 객실 문앞에서 현재 열쇠를 넣어 보고 안 맞으면 다음 열쇠를 넣어 보고 하는 식으로 해야 한다.

객실 복도 역시 원형으로 연결되어 있어 N번 객실 다음이 1번 객실 이다. 방문하는 모든 객실은 가지고 있는 열쇠중에 객실번호와 맞는 하나로만 열고 잠글 수 있다. 또한 준혁이가 모르는 사실하나는 이 테스트가 준혁이의 인내와 끈기를 테스트하는 것이라고 한다. 준혁이는 끈기있는 사람이라 테스트가 끝날때까지 한 마디 말도 없이 묵묵히 임무를 수행한다. 끝나고 나서 한 마디 하는데 “지금까지 객실문 열고 잠그기 시도에서 실패한 횟수의 총합은 몇 번일까?”라고 혼자말을 한다. 고생한 준혁이를 위하여 이 궁긍즘을 해결해주자.

입력 예 2번을 보자. 객실수(열쇠수)는 4개이고 객실문 열고 잠그기 실기 테스트 회수는 6이다. 열쇠고리에 주어진 열쇠 순서는 4, 2, 1, 3이다. 1번 객실을 열어야 하므로 4, 2, 1, 3 두 번 실패 후 성공, 열쇠 순서는 1, 3, 4, 2 가 된다. 2번 객실을 열어야 하므로 1, 3, 4, 2 세 번 실패 후 성공, 열쇠 순서는 2, 1, 3, 4 가 된다. 3번 객실을 열어야 하므로 2, 1, 3, 4 두 번 실패 후 성공, 열쇠 순서는 3, 4, 2, 1 이 된다. 4번 객실을 열어야 하므로 3, 4, 2, 1 한 번 실패 후 성공, 열쇠 순서는 4, 2, 1, 3 이 된다. 1번 객실을 열어야 하므로 4, 2, 1, 3 두 번 실패 후 성공, 열쇠 순서는 1, 3, 4, 2 가 된다. 2번 객실을 열어야 하므로 1, 3, 4, 2 세 번 실패 후 성공, 열쇠 순서는 2, 1, 3, 4 가 된다. 따라서 실패횟수의 합은 13번이 된다.