N 개에서 M개를 선택하기(N>=M)

얼마전에 코테를 봤는데 개털렸다

 

N 개 중에 M개를 못뽑는 바보가 여기있다.

 

결론부터 말하자면 재귀를 사용해서 구해주면 된다.

 

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

이 문제를 풀어보자

 

M개의 가게를 선택하고, 그 조합으로 계산을 해주면 되는 아주 간단한 문제이다. 근데 조합 못구하면 못품

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


struct store {
	int y;
	int x;
	bool checked;
};

vector<pair<int, int>> houses;
vector<store> stores;
vector<int> selected;
int N, M;
int ans = 1e9;

void calculateDistance() {
	int total = 0;
	for (int i = 0; i < houses.size(); i++) {
		int houseY = houses[i].first;
		int houseX = houses[i].second;
		int currentMin = 1e9;
		for (int j = 0; j < stores.size(); j++) {
			if (stores[j].checked) {
				// 우리 식당 정상 운영합니다
				int storeY = stores[j].y;
				int storeX = stores[j].x;
				int dist = abs(storeY - houseY) + abs(storeX - houseX);
				currentMin = (currentMin > dist) ? dist : currentMin;
			}
		}
		total += currentMin;
	}
	ans = (ans < total) ? ans : total;
}

void do_selection(int index, int count) {
	// dfs + 조합
	// 폐업시키지 않을 치킨집 최대 M개 고르기
	if (count == M) {
		calculateDistance();
	}
	for (int i = index; i < stores.size(); i++) {
		if (!stores[i].checked) {
			stores[i].checked = true;
			do_selection(i, count + 1);
			stores[i].checked = false;
		}
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			int temp;
			cin >> temp;
			if (temp == 1) {
				//house!
				houses.push_back({ y,x });
			}
			if (temp == 2) {
				
				stores.push_back(
					{ y,x,false }
				);
			}
		}
	}
	do_selection(0, 0);
	cout << ans << "\n";
	return 0;
}

 

void do_selection(int idx, int cnt){

  // cnt 가 원하는 만큼 뽑아졌는지 확인 -> 만약 그렇다면 조합을 다 뽑은 거니깐 그 다음 작업을 수행

 // idx> 부터 남아 있는 iter를 확인

 // 방문 여부를 확인

 // 방문 안했으면?

   -> 방문 체크하고

   -> do_selection(i, cnt++)

 // 아무튼 돌고 와서

   -> 방문 여부를 해제하고

}

 

진짜 이런 문제 한번 더 틀리면 사람이 아니다.