[백준] 1090번 : 체커 (C++)

10984번: 내 학점을 구해줘

---

문제)

N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 움직이는 것이다.

 

 

 

입력 :

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 체커의 x좌표와 y좌표가 주어진다. 이 값은 1,000,000보다 작거나 같은 자연수이다.

 

 

 

 

출력 :

첫째 줄에 수 N개를 출력한다. k번째 수는 적어도 k개의 체커가 같은 칸에 모이도록 체커를 이동해야 하는 최소 횟수이다.

 

 

 

 

 

풀이)

 

// 1090. 체커
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <climits>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    // 0개의 체커가 같은 위치로 모이도록 하기 위한 최소 횟수
    vector<int> move;
    move.resize(n + 1, INT_MAX);
    
    // 각 체커의 위치
    vector<pair<int, int>> checker;
 
    int a, b;
    for(int i = 0; i < n; i++)
    {
        cin >> a >> b;
        checker.push_back(make_pair(a, b));
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // (x, y) 위치로 체커를 모은다. 최대 50 * 50 = 2500
            int x = checker[i].first;
            int y = checker[j].second;
            
            // (x, y)로 가기위한 각 체커의 이동거리
            vector<int> dist;
            for (int k = 0; k < n; k++)
            {
                // k번째 체커의 이동거리
                int move = abs(x - checker[k].first) + abs(y - checker[k].second);
                dist.push_back(move);
            }
 
            // 정렬
            sort(dist.begin(), dist.end());
 
            // K개의 체커가 (x, y)로 모이기 위한 횟수
            for (int k = 1; k < n + 1; k++)
            {
                int a = accumulate(dist.begin(), dist.begin() + k, 0);
                // 각 횟수는 항상 최소값으로 유지한다.
                move[k] = min(move[k], a);
            }
        }
    }
 
    for (int i = 1; i < n + 1; i++)
    {
        cout << move[i] << " ";
    }
 
    return 0;
}
 

 

 

---

출처 : https://www.acmicpc.net/problem/1090 

1090번: 체커