N = int(input())
data = sorted(map(int,input().split()))
truck,heli = map(int,input().split())
prefix = [0]
for i in range(N):
prefix.append(prefix[-1]+data[i]*truck)
DP = prefix[:]
for end in range(1,N+1):
for start in range(1,end+1):
mid = (start+end)//2; r = (start+end)%2
DP[end] = min(DP[end],DP[start-1]+heli+prefix[end]-prefix[mid]-prefix[mid-1]+prefix[start-1]-r*data[mid-1]*truck)
print(DP[-1])DP 문제이다.
점화식을 세우는게 까다로운 문제였다.
풀이를 설명하면,
1. 물건을 옮겨야하는 장소를 거리순으로 정렬한다.
2. 거리순으로 1~N번 물건까지 모든 물건을 옮기는데 걸리는 비용을 누적합으로 저장한다.
3. DP 배열을 만든다. DP[n]은 n번째 물건까지 옮기는데 드는 최소비용을 의미한다.
4. 헬기로 옮길 시작점과 끝점에 대해 2중 for문을 돌며 최솟값을 구한다. start~end 까지의 물건을 헬기로 한번에 옮기는데 드는 비용 + DP[start-1]의 최솟값이 곧 DP[end]이다.
5. 최솟값을 출력한다.
이때 4번에서 start~end까지의 물건을 한번에 옮기는데 드는 최소비용은 start와 end의 중간값으로 start~end 물건을 헬기로 옮기고 트럭으로 옮기는 비용이다. 중간값에서 움직이면서 값의 변화량을 확인하면 왜 그때가 최소인지 알 수 있다.
또 1번에서 입력값이 오름차순으로 주어지지 않기 때문에 정렬하는 과정을 꼭 거쳐야한다.
오늘의 교훈) 입력값을 항상 체크하자