반응형
[문제링크]
https://www.acmicpc.net/problem/2141
[문제]
수직선과 같은 일직선상에 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를 출력한다.
이 문제는 2285번 문제와 동일한 문제이다.
수학을 알면 쉬운 문제이지만, 문제를 이해하는데 조금 많은 시간이 걸렸다..
백준 알고리즘 2141번 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;
}
}
}
궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.
반응형
'알고리즘 > 정렬' 카테고리의 다른 글
BJ_S5_2751_수 정렬하기 2 - Java (0) | 2022.04.28 |
---|---|
BJ_S5_11004_K번째 수 - Java (0) | 2022.02.01 |
BJ_G4_2285_우체국 - Java (0) | 2022.02.01 |
BJ_B3_10817_세 수 - Java (0) | 2022.02.01 |
BJ_S5_11651_좌표 정렬하기 2 - Java (0) | 2022.01.21 |
댓글