BOJ_14400_편의점 2 (Java, C++)

[Silver II] 편의점 2 - 14400

문제 링크

성능 요약

메모리: 46920 KB, 시간: 896 ms

분류

기하학, 수학, 정렬

제출 일자

2024년 12월 4일 17:28:10

문제 설명

영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고객들이 어느 위치에 존재하는지 파악을 하였고, 모든 고객들의 거리의 합을 최소로 하려한다. 두 위치 (x1, y1), (x2, y2)의 거리는 |x1 - x2| + |y1 - y2|로 정의한다.

n명의 주요 고객들의 위치 (x_i, y_i)이 주어질 때, 모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

입력

첫째 줄에는 주요 고객들의 수 n이 주어진다.

다음 n줄에는 i번 고객의 위치 x_i, y_i가 주어진다.

출력

모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

문제풀이

코드

Java코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	
	class Coordinate implements Comparable<Coordinate>{
		int x, y;
		public Coordinate(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override
		public int compareTo(Coordinate o) {
			if(this.x == o.x) return this.y - o.y;
			return this.x - o.x;
		}
	}
	
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		Coordinate[] coordinate = new Coordinate[N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			coordinate[i] = new Coordinate(x, y);
		}
		
		Arrays.sort(coordinate, (o1, o2) -> o1.x - o2.x);
        int pos_x = coordinate[N/2].x;
        
        Arrays.sort(coordinate, (o1, o2) -> o1.y - o2.y);
        int pos_y = coordinate[N/2].y;
		
		long res = 0;
		for(int i=0; i<N; i++) {
			res += (int) (Math.abs(coordinate[i].x - pos_x) + Math.abs(coordinate[i].y - pos_y));
		}
		
		bw.write(String.valueOf(res));

		bw.flush();
		bw.close();
		br.close();
	}
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int n;
vector<pair<int, int>> board;

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        board.push_back({x, y});
    }

    vector<int> pos_x;
    for (auto& p : board) {
        pos_x.push_back(p.first);
    }
    sort(ALL(pos_x));
    int mid_x = pos_x[n / 2];

    vector<int> pos_y;
    for (auto& p : board) {
        pos_y.push_back(p.second);
    }
    sort(ALL(pos_y));
    int mid_y = pos_y[n / 2];

    ll res = 0;
    for (const auto& p : board) {
        res += abs(p.first - mid_x) + abs(p.second - mid_y);
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}