말 교환 게임

시간 제한1초메모리 제한128 MB

요약

2n+1개의 칸에 흑과 백 폰이 n개씩 있고 가운데 한 칸이 비어 있을 때, 인접 이동과 상대 폰을 뛰어넘는 이동만으로 두 색을 모두 교환하는 최소 이동 수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

판은 번호가 매겨진 $2n + 1$ 개의 칸으로 이루어져 있습니다. 검은 말 $n$ 개와 흰 말 $n$ 개가 있습니다. 검은 말은 처음 $n$ 개의 칸(번호 $1$ 부터 $n$ 까지)에, 흰 말은 마지막 $n$ 개의 칸(번호 $n + 2$ 부터 $2n + 1$ 까지)에 놓여 있습니다. 처음에는 가운데 칸인 $n + 1$ 번 칸만 비어 있습니다.

게임 판
a. $n = 3$ 일 때의 처음 배치와 그때 가능한 이동
b. $5$ 번 칸의 흰 말을 옮긴 뒤의 판과 그때 가능한 이동

이동은 두 종류가 있습니다.

밀기: 말 하나를 바로 옆의 빈 칸으로 옮깁니다.
뛰어넘기: 말 하나가 바로 옆에 있는 다른 색 말 하나를 뛰어넘어, 그 너머의 빈 칸에 내려앉습니다.

목표는 두 색의 위치를 맞바꾸는 것입니다. 즉, 모든 검은 말은 $n + 2$ 번부터 $2n + 1$ 번까지의 칸으로, 모든 흰 말은 $1$ 번부터 $n$ 번까지의 칸으로 옮겨져야 합니다. 이 목표를 가능한 한 적은 이동 횟수로 달성하세요.

입력

한 줄에 정수 $n$ ( $1 \le n \le 100$ ) 하나가 주어집니다. $n$ 은 흰 말의 개수이자 검은 말의 개수입니다.

출력

처음 배치를 목표 배치로 바꾸는 데 필요한 최소 이동 횟수를 정수 하나로 출력하세요.

예제3

예제 1
입력
```
1
```
예상 출력
```
3
```
예제 2
입력
```
2
```
예상 출력
```
8
```
예제 3
입력
```
3
```
예상 출력
```
15
```