JOI 2019 본선- 동전모으기 > 문제은행 : 정보올림피아드&알고리즘




3378 : 동전모으기

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
7 회   
시도횟수
28 회   

문제

JOI 군은 엄청나게 큰 책상과 동전들을 갖고 있다. 

책상 여기저기에 놓여 있는 동전들을 가지런히 정리하려고 한다.

 책상은 2,000,000,001 * 2,000,000,001 크기의 격자로 이루어져 있다. 

행은 아래부터 위까지 –1,000,000,000 ~ 1,000,000,000의 번호가 매겨져 있다. 

열 또한 왼쪽부터 오른쪽까지 –1,000,000,000 ~ 1,000,000,000의 번호가 매겨져 있다. 

x번 행과 y번 열에 해당하는 칸을 (x, y)로 나타내자.

 책상 위에는 2N개의 동전이 있다. i번째(1≤i≤2N) 동전은 (Xi, Yi) 칸에 있다. 

JOI 군의 목표는 1≤x≤N, 1≤y≤2인 모든 (x, y) 칸에 동전이 하나씩 있게 하는 것이다.

 동전을 옮길 때는 동전 하나를 골라 인접한 칸으로 이동시키는 것을 반복한다. 

서로 변을 공유하는 두 칸을 인접하다고 한다. 여러 동전이 한 칸에 있을 수도 있다. 

JOI군이 목표를 이루기 위해 해야 하는 동전 이동 횟수의 최솟값을 출력하여라.

 

[입력 예 설명]

입력 예에서 동전의 위치는 다음과 같다.

 


 

 

JOI 군이 목표를 이루기 위해 하는 15번의 연산의 예시는 아래와 같다.

첫 번째 동전을 (0,0) -> (1,0) -> (1,1) -> (1,2)로 이동시킨다.

두 번째 동전을 (0,4) -> (1,4) -> (1,3) -> (2,3) -> (3,3) -> (3,2)로 이동시킨다.

세 번째 동전을 (4,0) -> (4,1) -> (3,1)로 이동시킨다.

네 번째 동전은 가만히 둔다.

다섯 번째 동전을 (2,5) -> (2,4) -> (2,3) -> (2,2)로 이동시킨다.

여섯 번째 동전을 (-1,1) -> (0,1) -> (1,1)로 이동시킨다.

 

14번의 연산으로는 목표를 이룰 수 없으므로 15를 출력한다.

 


입력형식

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 그 후 2N개의 줄에 동전의 좌표 Xi, Yi가 주어진다. (-1,000,000,000 ≤ Xi,Yi ≤ 1,000,000,000)

출력형식

JOI군이 목표를 이루기 위해 해야 하는 동전 이동 횟수의 최솟값을 출력한다.

입력 예

3
0 0
0 4
4 0
2 1
2 5
-1 1

출력 예

15

입력 예

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

출력 예

9

입력 예

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

출력 예

8000000029


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP