초반에 정보들만 잘 잡아둔다면 DP를 이용해서 쉽게 해결할 수 있다.
먼저, 모든 사람과 모든 계단까지 소요 시간을 미리 저장해둔다.
다음으로 DFS를 이용해서 모든 경우에 대해서, 모든 사람에게 계단을 할당해준다.
이제 0번 계단에 배정된 사람과, 1번 계단에 배정된 사람이 있다.
각각 벡터에 담아서, 계단에 빠르게 도착하는 사람이 앞으로 오도록 정렬해준다.
생각해보면, 계단을 사용하는 사람이 3명 이하라면 아무도 기다리지 않고, 도착하자마자 바로 계단으로 내려갈 수 있다.
하지만 계단을 이용하는 사람이 3명을 초과한다면, 경우에 따라서 대기를 하는 사람도 발생 할 수 있다.
예를들어 5번째에 도착한 사람이 있다. 그리고 현재 계단에는 3명의 사람이 있다고 쳐보자.
이 사람보다 3칸 앞에 있는 사람을 기다려야 한다면, 3칸 앞에 있는 사람이 탈출하자마자 들어가면 된다.
혹은, 3칸 앞에있는 사람을 기다릴 필요가 없다면, 즉, 자신이 도착하기도 전에 이미 3칸 앞에 있는 사람은 계단 밖으로 빠져나간 이후라면, 바로 계단에 도착하자마자 들어가면 된다.
이것을 DP로 구현해주면 된다.
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | #include<iostream> #include<algorithm> #include<vector> #include<cmath> #define INF 987654321 using namespace std; typedef pair<int, int> pii; struct Person { int idx; int dis0, dis1; pii pos; }; int n, map[11][11]; //i번 사람의 j번 계단까지 소요시간 vector<pii> stair; //계단 위치 vector<Person> people; int pickedStair[11]; //i번째 사람이 고른 계단 int Min = INF; int d[11]; bool cmp0(Person a, Person b) { return a.dis0 < b.dis0; } bool cmp1(Person a, Person b) { return a.dis1 < b.dis1; } void dfs(int k) { if (k == (int)people.size()) { vector<Person> use0, use1; //~번 계단 사용하는 사람들 for (int i = 0; i < k; i++) { if (pickedStair[i] == 0) use0.push_back(people[i]); else use1.push_back(people[i]); } //0번부터 sort(use0.begin(), use0.end(), cmp0); for (int i = 0; i < use0.size(); i++) { if (i < 3) //세명 이하라면 입구 도착 시간 + 계단 내려가는 시간 d[i] = use0[i].dis0 + map[stair[0].first][stair[0].second]; else { //if가 계단 꽉차서 기다려야 하는 경우 if (use0[i].dis0 < d[i - 3]) d[i] = d[i - 3] + map[stair[0].first][stair[0].second]; else //도착하자마자 계단에 들어갈 수 있는 경우 d[i] = use0[i].dis0 + map[stair[0].first][stair[0].second]; } } int time0 = d[use0.size() - 1] + 1; for (int i = 0; i < use0.size(); i++) d[i] = 0; //1번 sort(use1.begin(), use1.end(), cmp1); for (int i = 0; i < use1.size(); i++) { if (i < 3) d[i] = use1[i].dis1 + map[stair[1].first][stair[1].second]; else { if (use1[i].dis1 < d[i - 3]) d[i] = d[i - 3] + map[stair[1].first][stair[1].second]; else d[i] = use1[i].dis1 + map[stair[1].first][stair[1].second]; } } int time1 = d[use1.size() - 1] + 1; //대기 시간 추가 for (int i = 0; i < use1.size(); i++) d[i] = 0; int tmp = max(time0, time1); if (tmp < Min) Min = tmp; //초기화 use0.clear(); use1.clear(); return; } for (int i = 0; i < 2; i++) { pickedStair[k] = i; dfs(k + 1); } } int main(void) { //setbuf(stdout, NULL); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; for (int t = 1; t <= T; t++) { cin >> n; int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; if (map[i][j] > 1) stair.push_back({ i, j }); //계단 추가 else if (map[i][j] == 1) { people.push_back({ cnt,0,0, {i, j} }); //사람 추가 cnt++; } } } //모든 사람의 계단까지 이동 시간 for (int i = 0; i < people.size(); i++) { for (int j = 0; j < 2; j++) { if (j == 0) people[i].dis0 = abs(people[i].pos.first - stair[j].first) + abs(people[i].pos.second - stair[j].second); else people[i].dis1 = abs(people[i].pos.first - stair[j].first) + abs(people[i].pos.second - stair[j].second); } } dfs(0); cout << "#" << t << ' ' << Min << '\n'; //초기화 Min = INF; people.clear(); stair.clear(); } return 0; } | cs |
'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글
| SWEA 2117: 홈 방범 서비스 (C++) (0) | 2019.10.16 |
|---|---|
| SWEA 2382: 미생물 격리 (C++) (0) | 2019.10.16 |
| SWEA 4014: 활주로 건설 (C++) (0) | 2019.10.15 |
| SWEA 2105: 디저트 카페 (C++) (0) | 2019.10.15 |
| SWEA 5656: 벽돌 깨기 (C++) (0) | 2019.10.14 |