<SW>/알고리즘 + 자료구조
[삼성SWTest준비] 15686번 치킨 배달
Hading
2018. 10. 18. 00:48
728x90
URL : https://www.acmicpc.net/problem/15686
삼성SW 기출 문제 한 번에 보기 : https://www.acmicpc.net/workbook/view/1152
※삼성 SW 역량평가 기출문제 어떻게 풀지?※
- 아직.... 시간초과 때문에 해결이 안됨....
1. 문제 이해
- 도시 치킨 거리 = 모든 집의 치킨 거리 합
- 시간 복잡도 O(집의 갯수 * 치킨 집 C(조합) M)
- 관점으로 집을 기준? or 치킨집을 기준?(나는 치킨집을 기준)
2. 어떻게 품?
- 재귀함수로 치킨집 개수를 바탕으로 순열 만든다.
- 치킨집 폐업 수에 다다르면 지도를 갱신하여 도시 치킨 거리를 구하고 최소값을 저장
※필요 역량 정리하기!!!※
1. 브루트 포스
2. 재귀를 통한 순열
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include<iostream> #include<vector> #include<utility> #include<algorithm> using namespace std; int n, m; int map[51][51]; int visit[51][51] = { 0 }; int Min = 9999999; struct info { int x; int y; bool out; }; vector<info> chicken; vector<pair<int, int> > home; int distance(int x1, int y1, int x2, int y2) { int x, y; if (x1 > x2) { x = x1 - x2; } else { x = x2 - x1; } if (y1 > y2) { y = y1 - y2; } else { y = y2 - y1; } return x + y; } void check() { // 음식점 갯수 체크 int home_size = home.size(); int chicken_size = chicken.size(); for (int j = 0; j < chicken_size; j++) { if (chicken[j].out == true) continue; else { for (int i = 0; i < home_size; i++) { visit[home[i].first][home[i].second] = distance(chicken[j].x, chicken[j].y,home[i].first, home[i].second); } } } int ret = 0; for (int i = 0; i < home_size; i++) { ret += visit[home[i].first][home[i].second]; } Min = min(Min, ret); } void go(int index) { // 치킨집 폐업에 따라 진행(순열) int chicken_size = chicken.size(); int chicken_out = chicken.size() - m; if (chicken_out == index) { check(); return; } for (int i = index+1; i < chicken_size; i++) { chicken[i].out = true; go(index + 1); chicken[i].out = false; } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> map[i][j]; if (map[i][j] == 2) { chicken.push_back({i,j,false}); } else if (map[i][j] == 1) { home.push_back(make_pair(i, j)); } visit[i][j] = 99999999; } } go(0); /* int home_size = home.size(); for (int i = 0; i < home_size; i++) { ret += visit[home[i].first][home[i].second]; } cout << endl; cout << endl; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << visit[i][j]<<" "; } cout << endl; } */ cout << Min; return 0; } | cs |
728x90