pshpark12345님의 게시글

질문&답변

3-A 문제 풀이 관련 질문

#include using namespace std; vector > house; vector > chicken; vector > visited; int N,M; int chicken_cnt, house_cnt; int min_cnt = INT_MAX; int calculate(int house_idx, int chicken_idx) { int y = house[house_idx].first - chicken[chicken_idx].first; int x = house[house_idx].second - chicken[chicken_idx].second; if (y y *= -1; if (x x *= -1; return y + x; } void dfs(int idx, int distance, vector live_chicken) { if (idx > house_cnt-1) { min_cnt = min(min_cnt, distance); return; } for (int i=0; i if (visited[idx][live_chicken[i]] == 1) continue; visited[idx][live_chicken[i]] = 1; int plus_distance = calculate(idx, live_chicken[i]); distance += plus_distance; dfs(idx+1, distance, live_chicken); distance -= plus_distance; visited[idx][live_chicken[i]] = 0; } } void combi(int start, vector b, int k){ if(b.size() == k){ dfs(0, 0, b); return; } for (int i=start+1; i b.push_back(i); combi(i, b, k); b.pop_back(); } return; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for (int i = 0; i for (int j = 0; j int temp; cin >> temp; if (temp == 1) { house.push_back(make_pair(i, j)); } else if (temp == 2) { chicken.push_back(make_pair(i, j)); } } } chicken_cnt = chicken.size(); house_cnt = house.size(); for (int i = 0; i visited.push_back(vector ()); for (int j = 0; j visited[i].push_back(0); } } vector live_chicken; combi(-1, live_chicken, M); cout return 0; } 늦게봐서 죄송해요. 여깄습니다!