인프런 커뮤니티 질문&답변
작성한 질문수
3-A 반례를 알고 싶습니다
해결된 질문
작성
·
352
0
http://boj.kr/2ee36f4f84574c92a5029deb708602c6
일반 가정 집과 치킨 집 좌표를 구해두고 거리를 구한 다음 y에는 가정집 기준, x에는 치킨집 기준의 거리를 2차원 vector d에 넣어줬습니다.
최소값을 구해야하기 때문에 같은 x의 y값( 즉, 치킨집을 기준으로 모든 집과의 거리)의 합을 구하여 v vector에 넣었습니다. v는 <치킨집번호, 총거리의합>으로 담았습니다.
--> 이제 v[1].first에는 1번 치킨집이라는 정보, v[1].second에는 1번 치킨집과 모든 집과의 거리의 합이 들어가게 됩니다.
v를 v.second(치킨집과 각 집의 총거리의 합)를 비교하는 함수로 sort하고 m만큼 반복(입력한 남아 있을 최대 치킨 집의 수) 가정집과 first(치킨집번호)에 해당하는 거리를 min 함수를 이용하여 최소값을 구한 뒤 ret에 더해줍니다.
TC 모두 통과하기도 했고 논리적으로 오류가 없다고 생각했는데 틀렸다고 하여 반례 질문드립니다! 설명이 너무 장황했다면 죄송합니다ㅜ
답변 1
0
안녕하세요 재찬님ㅎㅎ
제가 주석을 좀 달았는데요. 답변 부탁드립니다.
#include <bits/stdc++.h>
using namespace std;
int a[54][54];
vector <pair<int,int>> house;
vector<pair<int,int>> chicken;
vector<int> d[104];
vector<pair<int,int>> v;
int n,m,ret,first,result;
bool cmp(pair<int,int>a, pair<int,int> b){
return a.second < b.second;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> a[i][j];
if(a[i][j] == 1) house.push_back({i,j});
else if(a[i][j] == 2) chicken.push_back({i,j});
}
}
int num = 1;
//집1 - (치킨 전부의 거리의 배열) 1 : n배열
for(pair<int,int> a : house){
for(pair<int,int> b : chicken){
int y,x;
if(a.first > b.first)y = a.first - b.first;
else y = b.first - a.first;
if(a.second > b.second) x = a.second - b.second;
else x = b.second - a.second;
d[num].push_back(x+y);
}
num++;
}
// 집 num - 1에 해당하는 치킨집의 수?
// 를 왜 굳이 chickenHouseNum에 넣죠?
// 저건 그냥 치킨집의 전체 수가 들어갈텐데요.
int chickenHouseNum = d[num-1].size();
for(int j = 0; j < chickenHouseNum; j++){
int total = 0;
for(int i = 1; i < num; i++){
total += d[i][j];
}
v.push_back({j, total});
}
// v에는 해당 치킨집의 넘버1, (집1 - 치킨1), (집2 - 치킨1) 의 거리가 담김
// 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.
// 이거는 어디에 구현이 되어있나요?
sort(v.begin(), v.end(), cmp);
// 도시에 있는 치킨집 중에서 최대 M개를 고르고
// 는 어디에 구현이 되어있나요?
for(int i = 1; i < num; i++){
result = 1000000;
for(int j = 0; j < m; j++){
int mn = d[i][v[j].first];
result = min(mn, result);
}
ret += result;
}
cout << ret << '\n';
}
--> 이게 문제 풀 때 설계하면서 사용했던 내용입니다..ㅜ안녕하세요 재찬님 ㅎㅎ
재찬님의 코드는 이런거죠?
d[집번호] {치킨1, 치킨2... }
그리고 그 담에
v{0, 0번째 치킨의 모든 집의 전체적거리}, {1, ...}
그 담에 sort를 해서
"평균적"으로 집에 가까운 치킨집이 앞에 위치하게 하는것이죠?
그리고 그 앞에 있는 것중에서 m개를 뽑아서 하는 건데,
이건 모든 경우의 수중에서 m개가 아니라 "평균적"으로 집에 가까운 치킨집이 최적해라는 재찬님의 그리디한 발상이 담겨있는 것 아닌가요?
그런 그리디한 발상, 너무 좋습니다만. 증명할 수 있나요?
평균적으로 모든 집에 가까운 치킨집 M개를 고르면 최적해라는 것이요.
그리디는 이런 증명이 어렵다. 또는 몇개의 예제는 맞아도 반례가 나타날 확률이 많다. 등의 이유로 먼저 1. 모든 경우의수를 기반한 로직 >> 그게 안되면 그담에 dp, 그리디 등을 쓰는게 일반적입니다.
또한 이 문제는 모든 경우의 수를 기반해서 로직을 구현해도 시간초과가 나지 않기 때문에 경우의 수를 기반으로 푸는게 좋습니다.
그리고 코드요.
불필요한 변수가 너무 많습니다.
int num = 1; 굳이 num을 쓸 이유는 없습니다.
for i = 0... 해서 이걸 이용하는게 낫지 않나요?
int chickenHouseNum = d[num-1].size();
이거요. 이 d[num - 1].size요. 이거 그냥 chicken.size()
아닌가요?감사합니다.
재찬님 그리고. 이 코드요.
반례가 있는데요.
예를 들어 전체 집까지의 평균거리가 짧은 치킨집이 앞에 m개가 설정되어있는데.
해당 집번호와는 거리가 먼 치킨집이 골라질수도 있지않을까요?
for(int i = 1; i < num; i++){
result = 1000000;
for(int j = 0; j < m; j++){
int mn = d[i][v[j].first];
result = min(mn, result);
}
ret += result;
}
안녕하세요 선생님!
왜 굳이 chickenHouseNum에 넣죠?
-->chickenHouse에 특정 변수를 담는 이유는 반복문에서 j의 반복 횟수를 d[].size()로 설정했더니 오류가 발생해서 특정 변수를 담았습니다!
치킨 거리가 가장 가까운 치킨 집 사이의 거리이다
--> 이 부분은 아래 설명 드릴 코드에 녹아 있다고 생각했습니다!
도시에 있는 치킨집 중에서 최대 M개를 고르는 구현은 어디에 있나요?
--> v에 <치킨집의 번호, 거리의 합>이 담기는데 이를 거리의 합 기준으로 정렬하게 된다면 최솟값을 가질 수 있는 치킨집 순서대로 정렬이 된다고 생각합니다.
for(int i = 1; i < num; i++){ result = 1000000;for(int j = 0; j < m; j++){int mn = d[i][v[j].first];result = min(mn, result); }ret += result; }위 코드처럼 선택할 최대의 치킨 집의 갯수만큼 뽑은 다음, v의 first는 치킨집 번호니까 해당 치킨집 번호와 집들의 거리를 확인해보며 최솟값을 담으면 위에서 여쭤보신 코드도 담겨있다고 생각합니다!