[BOJ][백준] 5042번: 나무 옮기기

https://www.acmicpc.net/problem/5042

5042번: 나무 옮기기

 

문제

"드디어 마지막 나무다!!"

세계적인 갑부 최백준의 정원 관리사 상근이가 외친 말이었다. 백준이네 집의 입구부터 분수까지 거리는 L미터이다. 입구와 분수 사이에는 일직선 도로가 있고, 도로의 폭은 W미터이다.

백준이는 상근이에게 도로의 양쪽에 나무를 심으라고 했다. 가장 첫 나무는 도로의 시작 지점에 있어야 하고, 마지막 나무는 끝 지점에 있어야 한다. 도로의 양쪽에 있는 나무의 위치는 모두 일치해야 한다. 또, 한쪽 면에 있는 모든 나무 사이의 거리는 같아야 한다.

상근이는 백준이의 말을 정확하게 듣지 않았고, 도로의 왼쪽에만 나무를 심었다. 상근이는 나무를 옮겨 백준이의 요구사항 대로 나무를 심으려고 한다. 백준이의 요구사항을 지키기 위해 옮겨야 하는 나무의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 심은 나무의 수 N이 주어진다. N은 짝수이며, 4보다 크거나 같고, 2000보다 작거나 같다. 다음 줄에는 두 정수 L과 W가 주어진다. (1 ≤ L ≤ 10000, 1 ≤ w ≤ 20)  다음 N개 줄에는 나무의 위치 p가 한 줄에 하나씩 주어진다. (0 ≤ p ≤ L)

출력

백준이의 요구사항을 지키기 위해 옮겨야 하는 나무의 이동거리의 최솟값을 출력한다. 정답과의 절대/상대 오차가 10^6 이내인 경우에 정답으로 인정된다.

 

---

 

기본적으로는 dp를 사용하는 문제입니다. 한번 아이디어를 캐치하면 코드작성은 어렵지 않게 할 수 있습니다. 움직이는 이미지이면 이해가 쉬울 거 같아 만들어봤습니다. 처음 왼쪽에 일렬로 정렬되어있는 나무 위치가 배열로 저장되어있다고 가정했을 때, 가장 시작점에 가까운 나무부터 차례대로 left 또는 right 지정되어있는 점에 저장을 하면 됩니다.

left배열에 저장을 할 때는 단순히 좌표 차이를 거리로 계산하면 되지만, right배열에 저장할 때는 피타고라스 이용해서 sqrt함수 사용하면 됩니다. 또 dp함수에 들어가기 전에 전처리 해 줄게 있죠? 전체 길이 L을 N/2개의 지점으로 나눠 좌표를 toSeed에 저장하는 반복문을 다음과 같이 작성해줍시다.

toSeed[0]=0.0;
for(int i=1;i<N/2;i++)
	toSeed[i]=toSeed[i-1]+(double)L/(N/2-1);

여기서 주의할 점은 L(N/2-1) 계산할 때 앞에 double형을 안 붙여주면 실수 오차가 발생하게 됩니다. 간단하게 L이 100이고 N이 8일 때 toSeed의 배열 값은 {0,33,66,99}가 됩니다. 간단하지만 놓치기 쉬운 실수 계산 주의해줍시다.

#include <iostream>
#include <string.h>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <limits.h>
using namespace std;
int N,L,W;
const double INF=INT_MAX-100.0;
double cache[2002][2002];
vector<int>v;
vector<double>toSeed;

double f(int leftIdx,int rightIdx)
{
    int idx=leftIdx+rightIdx;
    if(idx==N)return 0.0;

    double&ret=cache[leftIdx][rightIdx];
    if(ret>-0.5)return ret;
    ret=INF;
    if(leftIdx!=N/2)
        ret=min(ret,f(leftIdx+1,rightIdx)+abs(toSeed[leftIdx]-(double)v[idx]));

    if(rightIdx!=N/2)
        ret=min(ret,f(leftIdx,rightIdx+1)+sqrt(pow(abs(toSeed[rightIdx]-(double)v[idx]),2)+(double)W*W));

    return ret;
}

int main()
{
    memset(cache,-1,sizeof(cache));
    
    cin>>N>>L>>W;
    v.resize(N);
    toSeed.resize(N/2);
    for(auto&i:v)cin>>i;
    sort(v.begin(),v.end());

    toSeed[0]=0.0;
    for(int i=1;i<N/2;i++)toSeed[i]=toSeed[i-1]+(double)L/(N/2-1);
    
    cout<<fixed;
    cout.precision(7);
    cout<<f(0,0);
}

  toSeed전처리가 끝났으면 dp함수를 적어가는 것은 어렵지 않습니다. dp함수에서 이번에 계산할 나무 인덱스는 leftIdx+rightIdx임이 자명합니다. 이 인덱스가 N일 경우 모든 나무를 좌표에 넣었으므로 종료하면 됩니다.

dp함수에 최적화할 수 있는 부분이 보이긴 하는데, 수행 시간이 나쁘지 않아 더 건드리진 않았습니다. 포스트를 보고 있는 여러분은 도전해 보시길 바랍니다.