/* 점심 시간 밥을 빨리 먹기 위해 빠른 시간 내에 내려감 계단입구를 에스 사람은 피 1. 계단 입구까지 이동 시간 2. 계단을 내려가는 시간(동시에 3명만 올라갈 수 있습니다.) 계단의 길이가 주어집니다. 모든 사람들이 계단을 내려가 이동이 완료되는 시간이 최소가 되는 경우 계단1, 계단2 로 나누어서, 최대값을 하나 선정하고, 최대값들 중에서 최소값을 정하면 됩니다. 1. 계단 2개가 있는데 사람들이 나누어서 들어가는 경우를 생각하면 됩니다. 순열 2. 걸리는 시간대로 사람들을 줄을 세웁니다. 이것을 가지고 있는 하나의 큐를 만듭니다. 3. 큐에서 계단에 내려보냅니다. 이때, 계단은 3명까지 올라갈 수 있습니다. 계단 입구에서 대기줄을 받는 어레이 2개, 사람 번호, 도달 시간 계단 위에 올라와 있는 것 하나에 3개를 만들어 총 6개를 만듭니다. 사람 번호, 처음 들어갈 때 계단의 값을 더하고, 초가 지날 때마다, -- 처리하는 것을 하고, 계단이 비어 있으면, 대기줄에 있는 사람을 넣도록 합니다. 예제를 통해서 풀어보도록 하면 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 이런식으로 들어가도록 하겠습니다. 일단 나누는 dfs 를 하나 짜도록 하겠습니다. */ #include <iostream> #include <algorithm> #include <memory.h> using namespace std; #define SIZE 5 int map[SIZE][SIZE]; int ans, N; struct info { int num; // 사람수, 계단높이, int x; // 맵 x int y; // 맵 y }; int index = 1; int index2 = 1; info person[11]; info stair[2]; int person_stair[21] = {0,}; int waiting_1[10], waiting_2[10]; int cnt_1, cnt_2; void problemIn() { cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; if (map[i][j] == 1) { person[index].num = index; person[index].x = i; person[index].y = j; index++; } else if(map[i][j] != 1 && map[i][j] != 0){ stair[index2].num = index2; stair[index2].x = i; stair[index2].y = j; index2++; } } } } void init() { memset(person_stair, 0, sizeof(person_stair[0]) * 21); ans = 0; index = 1; index2 = 1; } /* 가져가야할 정보가 무엇인지 명확히 할 것, 들어갈 때, 먼저 1번을 1스테어에 넣고 시작해보고, 1번을 2스테이지에 넣고, 시작해보도록 하겠습니다. 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 2 3 4 5 6 번의 사람들을 1번 계단 대기에 넣습니다. 이때 필요한 변수가 무엇인가요? 도착시간에 따라서 솟팅을 한다음에 한명씩 내려보내야 합니다. 사람의 넘버는 더 이상 중요하지 않습니다. arr 에 습니다. 123456 사람들의 도착시간을 그리고 sort 를 합니다. */ void copy_arr(int a[21], int b[21]) { for (int i = 0; i < 21; i++) { b[i] = a[i]; } } /* 여기서 계단을 내려가는 연산을 하면 됩니다. */ void operand() { sort(waiting_1, waiting_1 + cnt_1); sort(waiting_2, waiting_2 + cnt_2); } void dfs(int depth, int pre_person_stair[21]) { int person_stair2[21]; copy_arr(pre_person_stair, person_stair2); if (depth == index-1) { // 예제에 따르면 index = 7 // 연산 처리 시작 cnt_1 = cnt_2 = 0; for (int i = 1; i < index; i++) { if (person_stair2[i] == 1) { waiting_1[i - 1] = abs(person[i].x - stair[1].x) + abs(person[i].y - stair[1].y); cnt_1++; } else { waiting_2[i - 1] = abs(person[i].x - stair[2].x) + abs(person[i].y - stair[2].y); cnt_2++; }
} operand(); return; } for (int i = 1; i <= 2; i++) { person_stair2[depth + 1] = i; dfs(depth + 1, person_stair2); } } void solve() { person_stair[1] = 1; dfs(1, person_stair); person_stair[1] = 2; dfs(1, person_stair); } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { init(); problemIn(); solve();
cout << "#" << tc << " " << ans << endl;
} } |
Programming/Algorithm