문제
정올 보드게임즈™는 프랙탈을 이용한 보드게임을 제작하였다.
이 게임은 N개의 말과 1개의 특별한 말, 방대한 게임판으로 이루어져 있다.
이 보드게임은 게임판 옆과 위에 숫자가 쓰여 있는데, 이는 행 번호와 열 번호를 의미한다.
위 그림에서 특별한 말(파란색)은 8행 0열에 있다.
한편, 게임판의 격자 색은 다음과 같은 방식으로 칠해져 있다.
0행에 해당되는 모든 칸과 0열에 해당되는 모든 칸은 흰색으로 칠해져 있다.
그 이외의의 칸에 대해서, 자기 바로 왼쪽 칸과 바로 위의 칸의 색이 같으면 검은색으로 칠해져 있으며, 그렇지 않다면 흰색으로 칠해져 있다.
이 보드게임은 크게 4가지 단계로 이루어진다.
우선 게임판에 N개의 말을 특정 위치에 놓는다. N개의 말을 놓는 곳은 모두 흰색 칸이다.
플레이어는 흰색 칸 중 임의의 한 곳(말이 있어도 상관없음)에 특별한 말을 놓는다.
플레이어는 N개의 말 중 하나를 상하좌우로 움직이면서 특별한 말이 있는 곳으로 움직인다. 이때 검은색 칸으로는 말을 움직일 수 없다.
이런 식으로 다른 플레이어들도 똑같은 방식으로 특별한 말을 놓고 게임을 진행한다. 최종적으로 말을 가장 적게 움직인 플레이어가 이긴다.
준형이는 친구들과 이 보드게임을 하면서 한 번도 이겨본 적이 없다. 그래서 준형이는 특단의 조치로 프로그래밍을 잘하는 친구인 당신에게 특별한 말을 어디에 놓아야 하는 지 코딩해달라고 한다.
입력
첫 번째 줄에는 말의 수 N이 주어진다.
두 번째 줄부터 N개의 줄에는 k번째(
출력
특별한 말을 적절히 배치했을 때, 말을 움직이는 횟수의 최솟값을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 22점 | N = 2, 0 ≤ Rk, Ck < 109 |
| #2 | 22점 | 2 ≤ N ≤ 100, 0 ≤ Rk, Ck < 109 |
| #3 | 28점 | 2 ≤ N ≤ 105, 0 ≤ Rk, Ck < 500 |
| #4 | 28점 | 2 ≤ N ≤ 105, 0 ≤ Rk, Ck < 109 |
예제 #1
2
2 1
4 3
6
예제 #2
6
2 5
3 4
8 7
9 6
10 5
11 4
50
로그인해야 코드를 작성할 수 있어요.