• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

맞는지 모르겠습니다

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

답변을 작성해보세요.

1

안녕하세요^^

문제에 보면

"도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재 하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다. "

라고 써져 있습니다. 님은 어떤 집의 "피자배달거리" 를 해당집과 모든 피자집과의 거리의 합으로 오해한 것 같습니다.  

문제에서는 어떤 집의 "피자배달거리" 는 해당집과 각 피자집과의 거리들 중 최소값을 그 집의 "피자배달거리"로 정의하고 있습니다.

그리고 도시의 피자배달거리는 모든 집의 "피자배달거리"를 합한 것입니다.

즉 이문제는 도시의 피자배달거리가 최소가 되도록 지도의 있는 피자집 중에서 살리고자 하는 M개의 피자집을 선택해야 하는 문제로 해석할 수 있습니다.

예리얼님의 프로필

예리얼

질문자

2021.03.01

감사합니다 코테 볼때도 이런 실수 많이했는데 어렵네요 ㅜㅜ