단계별로 무엇을 짜야할지 생각하고 풀면 쉬운 문제.
1. 치킨집 전체 개수에서 m개를 오픈할 때 모든 경우를 구하는 함수를 만들고
2. 1번에서 만들어진 경우에서 도시의 치킨 거리를 구하면서 최소값을 구한다.
코드
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 | #include<stdio.h> #include<vector> #include<iostream> #include<queue> #include<memory.h> #include<math.h> #include<algorithm> using namespace std; int map[51][51]; vector<pair<int, int>>home; vector<pair<int, int>>chick; bool tmp[14]; int n, m; int ans = 2000000000; int dist(int x, int y) { int min = 20000000; for (int i = 0; i < chick.size(); i++) { if (tmp[i] == true) { int cx = chick[i].first; int cy = chick[i].second; int d = abs(cx - x) + abs(cy - y); if (min > d) { min = d; } } } return min; } int go() { int sum = 0; for (int i = 0; i < home.size(); i++) { int x = home[i].first; int y = home[i].second; sum += dist(x, y); } return sum; } void open(int idx, int cnt) { if (cnt == m) { int a =go(); if (ans > a) { ans = a; } return; } if (idx >= chick.size()) { return; } tmp[idx] = true; open(idx + 1, cnt + 1); tmp[idx] = false; open(idx + 1, cnt); } int main() { //freopen("Text.txt", "r", stdin); cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; if (map[i][j] == 1) { home.push_back({ i,j }); } if (map[i][j] == 2) { chick.push_back({ i,j }); } } } open(0, 0); cout << ans << endl; } | cs |
'BOJ' 카테고리의 다른 글
백준 15683 / 감시 (0) | 2019.02.23 |
---|---|
백준 3568 / iSharp (0) | 2019.02.23 |
백준 15685 / 드래곤 커브 (0) | 2019.02.21 |
백준 2933 / 미네랄 (1) | 2019.02.21 |
백준 2422 / 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (0) | 2019.02.20 |