백준 1090 체커 (c++) : 피너클

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

1090번: 체커

완전탐색을 이용했다.

n = 5라면 

처음에는 체커 1개가 같은 칸에 모이도록 체커를 움직이는 횟수

두번째에는 체커 2개가 같은 칸에 모이도록 체커를 움직이는 횟수

이런식으로 출력하면 된다.

처음에는 문제를 이해 못해서 헤맸다.

int n;
vector<pair<int, int>> v;
vector<pair<int, int>> coord;

사용할 변수다.

coord에는 체커끼리 만나는 좌표가 들어간다.

cin >> n;
for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    v.push_back({ a, b });
}

main함수에서 값들을 입력받은뒤

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        coord.push_back({ v[i].first, v[j].second });

coord에 체커의 좌표로 만들수 있는 모든 좌표를 집어넣는다.

for (int i = 1; i <= n; i++) {
    int ans = 987654321;
    for (int j = 0; j < coord.size(); j++) {
        ans = min(ans, solve(i, j));
    }
    cout << ans << ' ';
}

그후 1부터 n까지 확인한다.

ans에 거대한 값을 집어넣은 다음 solve(i, j)를 돌리며 그중 가장 작은 값을 ans에 넣는다.

모든 coord좌표에 solve를 돌린뒤 ans를 출력하면 된다.

int solve(int k, int idx) {
    int mid_x = coord[idx].first;
    int mid_y = coord[idx].second;

solve함수는 k와 coord의 idx를 전달받는다.

mid_x와 mid_y에 coord[idx]값들을 집어넣는다.

    vector<int> dis;
    for (int i = 0; i < n; i++) {
        dis.push_back(abs(mid_x - v[i].first) + abs(mid_y - v[i].second));
    }
    sort(dis.begin(), dis.end());

그후 idx에 체커와 mid_x, mid_y의 거리를 집어넣고 정렬한다.

    int sum = 0;
    for (int i = 0; i < k; i++) sum += dis[i];
    return sum;
}

sum에 k만큼 dis[i]를 집어넣고 반환하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector<pair<int, int>> v;
vector<pair<int, int>> coord;

int solve(int k, int idx) {
	int mid_x = coord[idx].first;
	int mid_y = coord[idx].second;

	vector<int> dis;
	for (int i = 0; i < n; i++) {
		dis.push_back(abs(mid_x - v[i].first) + abs(mid_y - v[i].second));
	}
	sort(dis.begin(), dis.end());
	int sum = 0;
	for (int i = 0; i < k; i++) sum += dis[i];
	return sum;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a, b });
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			coord.push_back({ v[i].first, v[j].second });

	for (int i = 1; i <= n; i++) {
		int ans = 987654321;
		for (int j = 0; j < coord.size(); j++) {
			ans = min(ans, solve(i, j));
		}
		cout << ans << ' ';
	}
}

전체코드다.