3-A 문제 풀이 관련 질문

작성한 질문수 7

0

안녕하세요 ㅎㅎ

강사님이 강의에서 알려주신 코드와 시간복잡도를 비교해보려고 했는데

-> 많이 비효율적인 코드입니다.

지금 작성하신 코드는 치킨집 조합을 하나 고른 뒤, dfs로 각 집이 어떤 치킨집을 선택할지까지 전부 탐색하고 있고 이 때문에 각 조합마다 대략 M^(집의 수) 경우를 보게 됩니다.

예를 들어 집이 10개이고 선택한 치킨집이 5개라면, 한 조합마다 5^10개 경우를 보는 구조입니다. 이 문제에서는 각 집마다 “가장 가까운 치킨집”만 고르면 되기 때문에, 집마다 치킨집 선택 경우를 dfs로 나눌 필요가 없습니다.

dfs를 배운 이후부터는 뭔가 좀 복잡하다 싶으면 dfs부터

-> 음.. 그럴수있죠 ㅎㅎ 무식하게는 좋은데 무식하게 풀기 전에

모든 선택 경로를 실제로 나눠봐야 하는가?

이런 거를 좀 더 생각하고 하시면 좀 줄일 수 있으실거에요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> house;

vector<pair<int, int>> chicken;

vector<vector<int>> 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 < 0)

y *= -1;

if (x < 0)

x *= -1;

return y + x;

}

void dfs(int idx, int distance, vector<int> live_chicken) {

if (idx > house_cnt-1) {

min_cnt = min(min_cnt, distance);

return;

}

for (int i=0; i<live_chicken.size(); 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<int> b, int k){

if(b.size() == k){

dfs(0, 0, b);

return;

}

for (int i=start+1; i<chicken_cnt; 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 < N; i++) {

for (int j = 0; j < N; 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 < house_cnt; i++) {

visited.push_back(vector<int>());

for (int j = 0; j < chicken_cnt; j++) {

visited[i].push_back(0);

}

}

vector<int> live_chicken;

combi(-1, live_chicken, M);

cout << min_cnt << endl;

return 0;

}

늦게봐서 죄송해요. 여깄습니다!

0

안녕하세요 ㅎㅎ

코드 이미지 말고 코드로 다시 부탁드려도 될까요?

감사합니다.