https://swexpertacademy.com/main/main.do [2383] 점심 식사시간
N*N(<=10) Map이 주어진다. 사람들(<=10)이 1로 표기된다. 계단은 2개이며 1초과 10이하의 수로 표기된다. 사람들은 1분에 1칸씩 이동하며 계단위에 도착하면 1분이 지난 후에 계단을 내려갈 수 있다. 계단으로 주어진 수만큼의 분이 지나야 계단을 모두 내려간 것이다. 계단은 동시에 세 사람이상이 내려갈 수 없다. 모든 사람이 내려가는데 걸리는 최소 시간.
2^사람 * 시간 정도이므로 2^10 * 100 으로 최악의 상황에도 충분히 연산할 수 있다.
N*4 + a byte
-
사람들과 계단을 좌표 단위로 배열에 저장한다.
-
사람들마다 2개의 계단 중 어디 계단으로 갈 것인지를 선택한다.
-
계단 별로 계단과 사람과의 거리를 계산하여 배열에 저장한다.(사람이 6명이라면 계단1에는 1,2 사람, 계단2에는 3,4,5,6 사람 등 모든 경우의 수)
-
오름차순으로 정렬한다.
-
계단[1
3]는 거리(계단[13])+계단길이+1로 저장하고 계단[k] 는 계단[k-3]+계단길이 과 계단[k]+계단길이+1 중 더 큰 값을 저장한다. -
계단1, 계단2의 마지막 사람(거리가 가장 먼)의 거리 중 큰 값이 모든 사람이 계단을 내려가는 분이다.
사람들이 1번 계단으로 갈 지 2번 계단으로 갈 지를 선택해서 모든 경우의 수를 따져보면 된다. 선택을 DFS나 for문으로 구현한다. 선택이 모두 되면 계단 하나에 사람들이 배정된다. 거리 별로 오름차순으로 정렬할 수 있다. 계단 하나에 대해 오름차순으로 정렬된 사람들은 거리 순으로 계단에 들어가게 되는데 3명이 동시에 계단을 이용할 수 없다. 따라서 큐를 만들어 사람들을 넣어주며 시간이 흐를 때마다 큐의 데이터가 3이 넘지 않게 하며 모든 사람이 내려간 시간을 구할 수 있다. 다른 좋은 방법으로는 i번째 사람이 내려가기 위해서는 i-3번째 사람이 다 내려가야 하는 것을 이용하는 것이다. 첫번째부터 세번째 사람들이 완전히 내려가는 시간은 거리+1+계단길이가 된다. 네번째 사람은 첫번째 사람이 내려가야 내려갈 수 있으므로 (첫번째 사람이 완전히 내려간 시간+계단길이 or 네번째 사람의 거리(계단까지 오는데 걸리는 시간)+계단길이+1) 둘 중 큰 값이 네번째 사람이 완전히 내려가는데 걸리는 시간이 된다.
#include <stdio.h>
#include <math.h>
int dt[20][3], person[20][2], N, gae[2][3], min;
int main()
{
int T, i, j, k, l,ct, imsi, ct2, ct3, g, a, mina, minb;
scanf("%d", &T);
for (i = 1; i <= T; i++)
{
ct = 0;
ct2 = 0;
scanf("%d", &N);
for (j = 0; j < N; j++)
{
for (k = 0; k < N; k++)
{
scanf("%d", &imsi);
if (imsi == 1)
{
person[++ct][0] = j;
person[ct][1] = k;
}
else if (imsi > 1)
{
gae[ct2][0] = j;
gae[ct2][1] = k;
gae[ct2++][2] = imsi;
}
}
}
min = 9999;
g = pow(2, ct);
for (j = 0; j < g; j++)
{
mina = 9999;
minb = 9999;
a = j;
ct2 = 0;
ct3 = 0;
for (k = 1; k <= ct; k++)
{
if (a % 2 == 0)
{
dt[++ct2][0] = abs(person[k][0] - gae[0][0]) + abs(person[k][1] - gae[0][1]);
}
if (a % 2 == 1)
{
dt[++ct3][1] = abs(person[k][0] - gae[1][0]) + abs(person[k][1] - gae[1][1]);
}
a /= 2;
}
for (k = 1; k <= ct2 - 1; k++)
{
for (l = k+1; l <= ct2; l++)
{
if (dt[k][0] > dt[l][0])
{
imsi = dt[k][0];
dt[k][0] = dt[l][0];
dt[l][0] = imsi;
}
}
}
for (k = 1; k <= ct3 - 1; k++)
{
for (l = k + 1; l <= ct3; l++)
{
if (dt[k][1] > dt[l][1])
{
imsi = dt[k][1];
dt[k][1] = dt[l][1];
dt[l][1] = imsi;
}
}
}
if (ct2 < 3) mina = dt[ct2][0] + gae[0][2] + 1;
else
{
for (k = 1; k <= 3; k++) dt[k][2] = dt[k][0] + gae[0][2] + 1;
for (k = 4; k <= ct2; k++)
{
if (dt[k - 3][2] > dt[k][0]) dt[k][2] = dt[k - 3][2] + gae[0][2];
else dt[k][2] = dt[k][0] + gae[0][2] + 1;
}
if (mina > dt[ct2][2])mina = dt[ct2][2];
}
if (ct3 < 3) minb = dt[ct3][1] + gae[1][2] + 1;
else
{
for (k = 1; k <= 3; k++) dt[k][2] = dt[k][1] + gae[1][2] + 1;
for (k = 4; k <= ct3; k++)
{
if (dt[k - 3][2] > dt[k][1]) dt[k][2] = dt[k - 3][2] + gae[1][2];
else dt[k][2] = dt[k][1] + gae[1][2] + 1;
}
if (minb > dt[ct3][2]) minb = dt[ct3][2];
}
if (mina > minb) minb = mina;
else mina = minb;
if (min > mina) min = mina;
if (min > minb) min = minb;
}
printf("#%d %d\n", i, min);
}
}