BOJ 5042 나무 옮기기

BOJ 5042 나무 옮기기

[분류 - 다이나믹 프로그래밍]

  (문제 요약) 왼쪽 도로에 나무를 N / 2만큼, 오른쪽 도로에 나무를 N/2만큼 심어야하는데 어떻게 해야 최소로 나무를 움직이면서 계산할 수 있을지가 문제다.

 

[풀이]
  p번째 나무를 왼쪽 도로에 할당할지, 오른쪽 도로에 할당할지를 결정할 때 나올 수 있는 상태를 현재 왼쪽 도로에 할당할 수 있는 i번째 위치, 현재 오른쪽 도로에 할당할 수 있는 j번째 위치로 볼 수 있다.

 

rec = min(rec(i+1, j) + "왼쪽 도로 i번째에 할당할 때의 거리", rec(i, j+1) + "오른쪽 도로 j번째에 할당할 때의 거리")

(참고) p는 i + j로 구할 수 있다.

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX_N = 2e3;
int L, W, N, M, p[MAX_N];
double dp[1001][1001], d;
double gv(double a, double b, int w) {
    return sqrt((a - b) * (a - b) + w * w);
}
double rec(int l, int r) {
    if (l == M && r == M) return 0;
    double& ret = dp[l][r];
    if (ret != -1) return ret;
    ret = 1e9;
    if (l < M) ret = rec(l + 1, r) + gv(p[l + r], l * d, 0);
    if (r < M) ret = min(ret, rec(l, r + 1) + gv(p[l + r], r * d, W));
    return ret;
}
int main() {
    int i, j;
    scanf("%d%d%d", &N, &L, &W);
    M = N / 2;
    for (i = 0; i <= M; i++) for (j = 0; j <= M; j++) dp[i][j] = -1;
    for (i = 0; i < N; i++) scanf("%d", &p[i]);
    sort(p, p + N);
    d = L / (M - 1.);
    printf("%.8lf", rec(0, 0));
    return 0;
}