3378 : 동전모으기
- 제한시간
- 2000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 0 회
- 시도횟수
- 1 회
문제
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를 출력한다.
입력형식
출력형식
입력 예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 |