2796번 - 만남 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 77 | 39 | 33 | 47.826% |
문제
올해 여름에 종혁이는 친구들과 함께 락 페스티벌에 가려고 한다. 종혁이는 친구들의 티켓도 자신이 직접 구매했고, 이제 티켓을 친구들에게 배달하러 가려고 한다.
종혁이와 친구들이 살고 있는 마을은 이차원 평면으로 나타낼 수 있다. 종혁이는 정수 좌표 위에만 서 있을 수 있다. 종혁이가 현재 있는 좌표에서 인접한 여덟 개의 좌표 중 하나로 한 걸음에 이동할 수 있다. (위, 아래, 왼쪽, 오른쪽, 대각선)
종혁이의 친구는 티켓을 받으러 자신의 집에서 조금 걸어 나올 수 있다. 즉, 친구가 살고 있는 집의 좌표가 (x, y)이면, 집에서 P걸음 떨어진 곳까지 종혁이를 마중나올 수 있다. P는 각각의 친구에 따라서 다르다.
티켓을 모두 배달한 후에 종혁이는 배달한 순서를 다시 생각해 보았다. 이때, 종혁이가 걸었던 걸음의 최솟값을 구하는 프로그램을 작성하시오. 종혁이가 배달을 시작한 위치와 끝마친 위치의 좌표는 알 수 없다.
입력
첫째 줄에 친구의 수 N이 주어진다. (2 ≤ N ≤ 200,000)
다음 N개 줄에는 집의 위치 x, y와 P가 주어진다. (0 ≤ x, y, P ≤ 200,000)
종혁이가 티켓을 배달한 순서대로 입력이 주어진다.
출력
첫째 줄에 종혁이가 티켓을 배달하는데 필요한 걸음 수의 최솟값을 출력한다.
예제 입력 1
3 3 10 2 8 4 2 2 5 2
예제 출력 1
4
예제 입력 2
4 3 3 5 7 11 5 20 8 10 30 18 3
예제 출력 2
19
힌트
첫 번째 예제의 경우 배달을 (4, 8)에서 시작한다면, 첫 번째 친구를 만날 수 있다. 그 다음 (6, 6)으로 가서 두 번째 친구를 만나고, (4, 5)로 가서 세 번째 친구를 만나면 된다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호