아무리 생각해도 2중 for문을 안쓰고 문제를 해결할 수가 없다고 생각했는데 내 생각이 맞았던 문제다.
N번째 사람이 4번위치에 있을 때 케익을 0~4번위치에서 줄 수 있다.
따라서 N-1번째 사람에게 케익을 주고 N번째 사람에게 케익을 줄때 최단거리는 위와같이 위치 하나당 5가지의 경우 총 25가지 경우를 비교해서 각 위치의 최단거리를 저장하면된다.
#include <cstdio>
#include <algorithm>
#define MAX 987654321987
using namespace std;
unsigned long long dp[2][5];
int main(){
int N, X, Y;
int dx[5] = {-1,0,0,1,0}, dy[5] = {0,-1,1,0,0};
scanf("%d", &N);
scanf("%d %d", &X, &Y);
for (int n = 0; n < 2; n++)
for (int m = 0; m < 5; m++)
dp[n][m] = MAX;
for (int n = 1; n <= N; n++){
int cx, cy;
scanf("%d %d", &cx, &cy);
for (int i = 0; i < 5; i++){
if (cx + dx[i] >= 0 && cx + dx[i] <= 100000 && cy + dy[i] >= 0 && cy + dy[i] <= 100000){
if (n==1)
dp[n%2][i] = abs(cx + dx[i] - X) + abs(cy + dy[i] - Y); //빵집->첫번째 사람
else{
dp[n % 2][i] = MAX;
for (int j = 0; j < 5; j++)
dp[n%2][i] = min(dp[n%2][i],abs(cx + dx[i] - (X + dx[j])) + abs(cy + dy[i] - (Y + dy[j])) + dp[(n+1)%2][j]);
//n-1번째 사람->n번째 사람
}
}
}
X = cx; Y = cy;
}
unsigned long long ans = MAX;
for (int n = 0; n < 5; n++)
ans = min(ans, dp[N % 2][n]);
printf("%lld\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기