-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
맞는지 모르겠습니다
21.02.28 17:02 작성 조회수 102
0
선생님 저는 문제를 잘 이해하지 못한건지;; 이렇게 짰습니다
첫번째로 pizza라는 페어를 새로 만들어서 할당해도 괜찮은지 궁금합니다
그리고 강의에서는 dis = min(dis) 이렇게 하셨는데 이게 이해가 안갑니다
모든 집에서 선택된 피자가게까지의 거리를 더한 후에 그것의 min 값을 구하는 문제가 아닌가요..?
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, res;
vector<pair<int, int> > map[30];
pair<int, int> pizza[30];
dfs(int s, int L){
if(L==m){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
sum += abs(map[1][i].first-map[2][j].first) + abs(map[1][i].second-map[2][j].second);
}
}
if(res>sum) res=sum;
}
else{
for(int j=s;j<map[2].size();j++){
pizza[j] = map[2][j];
dfs(j+1,L+1);
pizza[j] = {0,0};
}
}
}
int main(){
int x;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&x);
if(x==1){
map[1].push_back(make_pair(i,j));
}
else if(x==2){
map[2].push_back(make_pair(i,j));
}
}
}
dfs(0,0);
return 0;
}
답변을 작성해보세요.
1
김태원
지식공유자2021.03.01
안녕하세요^^
문제에 보면
"도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재 하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다. "
라고 써져 있습니다. 님은 어떤 집의 "피자배달거리" 를 해당집과 모든 피자집과의 거리의 합으로 오해한 것 같습니다.
문제에서는 어떤 집의 "피자배달거리" 는 해당집과 각 피자집과의 거리들 중 최소값을 그 집의 "피자배달거리"로 정의하고 있습니다.
그리고 도시의 피자배달거리는 모든 집의 "피자배달거리"를 합한 것입니다.
즉 이문제는 도시의 피자배달거리가 최소가 되도록 지도의 있는 피자집 중에서 살리고자 하는 M개의 피자집을 선택해야 하는 문제로 해석할 수 있습니다.
답변 1