글 읽기 - 테스트 케이스 및 게시판에 올라온 반례들은 모두 맞습니다.

qkrgywjd456 2년 전 0

해결 idea또한 맞는거 같은데 왜 틀리는건지 모르겠습니다.

제가 무엇을 놓친걸까요????

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

int arr[51][51];
int res=987654321;
vector<string>list;
//치킨
vector<pair<int, int>>c;

//홈
vector<pair<int, int>>h;
int n,m;
//치킨집 수
int num=0;
//치킨 가게 선택 방법 고르기 (list 벡터에 저장)
void dfs(int index,int cnt,string lis,int cmp){
 
    if(index>=num||cnt>=cmp){
        if(cnt==cmp){
            list.push_back(lis);
        }
        return;
    }
    
   
    dfs(index+1,cnt+1,lis+to_string(index),cmp);
    dfs(index+1, cnt, lis,cmp);
}


int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
   
    cin>>n>>m;
   
    
    //입력 받음
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
            if(arr[i][j]==1){
                h.push_back({i,j});
            }else if(arr[i][j]==2){
                num++;
                c.push_back({i,j});
            }
        }
    }
    

    //최대 m개의 치킨 가게 선택
    //1~m개의 치킨 가게 선택방법 구하기
    for(int i=1;i<=m;i++){
        dfs(0,0,"",i);
    }
   
    
    //치킨 가게 선택 리스트
    for(int i=0;i<list.size();i++){
        string tmp=list[i];
        int sum=0;
        for(int k=0;k<h.size();k++){
            int t=987654321;
            for(int j=0;j<tmp.size();j++){
                t=min(t,abs(h[k].first-c[(tmp[j]-'0')].first)+abs(h[k].second-c[(tmp[j]-'0')].second));
            }
            sum+=t;
        }
        res=min(res,sum);
        
        
        
    }
    
    
    cout<<res<<"\n";
    
    
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

테스트 케이스 및 게시판에 올라온 반례들은 모두 맞습니다.

qkrgywjd456 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말