문제 링크 : https://www.acmicpc.net/problem/15686
해결 방법)
풀고나서 다른 해결방법들을 보니까 대게 비슷하게 푼것같다.
그래도 내가 푼 아이디어를 풀어보고자 한다. (누군가에게는 도움이 되겟지하는 생각에)
치킨집 고르는 경우 즉 M개(1개의 치킨집, 2개의 치킨집, 3개의 치킨집 ...... M개의 치킨집) 에서 모든 집들과의 거리중 최소거리만 구하여 이 최소거리의 합들이 우리가 구하고자하는 도시의 치킨거리값이 되는 것이다.
그런데 우리는 1개를 어떻게고르고 2개를 어떻게고르고에 대한 아이디어가 없당 ㅜ 이것은 재귀적으로 상황을 두개 만들어 주면 된다. 있고, 없고의 두가지상황인데 A,B,C의 치킨집이있다고하면,
A 있고 B 있고, C 없고
A 없고 B 있고 C 없고 .... 요론식으로 하다보면 모든 경우의수를 찾을 수 있다는 느낌을 받을 수 있다.
즉 각 치킨집마다 있고 없고의 상황 두가지를 만들어서 치킨집을 먼저 고를 수 있다.
이제 골라진 치킨집이 1개일때,2개일때 ,3개일때, 4개일때..... M개 이하 일때 마다 치킨 거리 총합을 알아야지 도시의 치킨거리를 알 수 가있는데 어떻게 골라진 치킨집 개수마다 그 치킨거리 총합을 알아낼 것인가가 문제이다.
이 해결방법은 모든 집마다 거리를 구하는데 골라진 집들과의 사이를 구하면서 최소값을 각 집마다 구해나가는 것이다.
우리는 각치킨집마다 경우를 있고,없고의 두가지 경우를 만들었는데, 이때 치킨집이 있다라면 이 치킨집은 골라진녀석이고 따로 골라졌다라는 표식을 남겨두면 나중에 골라진 치킨집에대해 거리값을 구해나갈수 있다.
따라서 골라진 치킨집과 모든 집들사이의 거리를 구할 수 있게되고 당연히 최소값도 구하게되면서 이 최소값들의 총합이 결국엔 우리가 구하는 답이 된다.
또 참고로 최대 M개라고해서 M개를 골랐을때만 왜 조건을 거냐라고 말할 수 있는데, 어차피 FOR문을 돌면 각집이 치킨집들 중 최소값만 지니기 때문에 하나의 치킨집만 선택된경우도 자연스레 포함이 되어 모든 경우를 내포하기때문이다.
소스코드)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #include<iostream> #include<vector> #include<cmath> using namespace std; int ans = 987654321; // 도시의 치킨거리 int M; int visit[13]; vector<pair<int, int>> home; // 집좌표 vector<pair<int, int>> chicken; // 치킨 좌표 int csize; int min(int a, int b) { return a < b ? a : b; } void solve(int inow, int cnt_now) { if (cnt_now == M) // 최대 M개를 고를때 { int d; // 두점사이의 거리 int x1, x2; int y1, y2; int tmp = 0; int homesize = home.size(); for (int i = 0; i < homesize; i++) { int minnum = 987654321; for (int j = 0; j < csize; j++) { if (visit[j]) { d = abs(home[i].first - chicken[j].first) + abs(home[i].second - chicken[j].second); if (minnum > d) minnum = d; } } tmp += minnum; } ans = min(ans, tmp); //도시치킨거리 갱신 return; } if (inow >= csize) return; visit[inow] = 1;// 현재 치킨집 선택 solve(inow + 1, cnt_now + 1); visit[inow] = 0; solve(inow + 1, cnt_now); } int main() { int N; int num; cin >> N >> M; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { scanf("%d", &num); if (num == 1) { home.push_back({ i,j }); } else if (num == 2) { chicken.push_back({ i,j }); } } } csize = chicken.size(); solve(0, 0); printf("%d\n",ans); } | cs |
'PS > 백준' 카테고리의 다른 글
| 2448번 별 찍기 - 11 (0) | 2018.11.12 |
|---|---|
| 1966번 프린터 큐 (0) | 2018.10.28 |
| 7576번 토마토 (0) | 2018.10.24 |
| 2839 설탕배달 (0) | 2018.10.19 |
| 14891번 톱니바퀴 (0) | 2018.10.15 |
