BJ_G4_2285_우체국 - Java

[문제링크]

https://www.acmicpc.net/problem/2285

2285번: 우체국

---

[문제]

수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.

이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.

각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다

---

[입력]

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

---

[출력]

첫째 줄에 우체국의 위치를 출력한다. 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.

---

[예제 입력 1]

3
1 3
2 5
3 3

---

[예제 출력 1]

2

 

---

[설명]

이 문제는 정렬 문제이다.

X를 기준으로 우선 정렬하고, 그 다음 A를 기준으로 정렬한다.

사람의 총 인원중 가운데번째 있는 사람의 위치에 우체국을 세우면 된다.

사람수를 처음부터 더하다가 중앙에 있는 사람의 위치가 해당 마을에 포함되게 되면 해당 마을의 X를 출력한다.

이 문제는 2141번 문제와 동일한 문제이다.

수학을 알면 쉬운 문제이지만, 문제를 이해하는데 조금 많은 시간이 걸렸다..

 

 

백준 알고리즘 2285번 JAVA풀이

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scann = new Scanner(System.in);
		int N = scann.nextInt();
		Node[] arr = new Node[N];
		long sum=0;
		long cnt=0;
		for(int i=0;i<N;i++) {
			long x=scann.nextLong();
			long a=scann.nextLong();
			arr[i]=new Node(x,a);
			cnt+=arr[i].a;
		}
		Arrays.sort(arr, new Comparator<Node>() {
			@Override
			public int compare(Node n1, Node n2) {
				if(n1.x==n2.x) return (int)(n1.a-n2.a);
				return (int)(n1.x-n2.x);
			}
		});
		for(int i=0;i<N;i++) {
			sum+=arr[i].a;
			if(sum>=(cnt+1)/2) {
				System.out.println(arr[i].x);
				break;
			}
		}
	}
	public static class Node{
		long x;
		long a;
		public Node(long x2, long a2) {
			super();
			this.x = x2;
			this.a = a2;
		}
	}
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.