백준 1866: 택배

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

 

오랜만에 고전하게 된 DP 문제다. 

처음에 떠올린 점화식은 다음과 같다.

DP[현재 위치][중심 위치] = min(DP[현재 위치 + 1][중심 위치] + 트럭비용 * (중심과 현재간 거리), DP[현재 위치][다른 위치] + 헬리콥터 위치)

 

단순하지만, 떠오르기 쉽지 않아서, 이게 답이다! 라며 돌진하였다. 안타깝게도, "시간 초과"란 결과를 얻었지만...

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int N, dp[3001][3001], P[3001], T, H;
int solve(int idx, int mid)
{
	if (idx > N) return 0;
	int& ret = dp[idx][mid];
	if (ret >= 0) return ret;
	ret = 1000000007;
	ret = min(ret, solve(idx + 1, mid) + abs(P[idx] - P[mid]) * T);
	for (int m = mid + 1; m <= N; m++) ret = min(ret, solve(idx, m) + H);
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> P[i];
	sort(P + 1, P + N + 1);
	cin >> T >> H;
	cout << solve(1, 0) << '\n';
}

결국엔 다른 아이디어가 필요해진 난 머리를 꽁꽁 매었지만, 새로운 아이디어가 떠올려지지가 않았다.

이 문제는 지금까지 푼 다른 문제들과는 달리, 시간을 정해놓고 고민을 해보고, 안 되면 구글링을 해보자고, 정했었기에, 결국 구글링을 거쳤다.

https://justicehui.github.io/koi/2019/01/15/BOJ1866/

백준1866 택배

DP 점화식은 다음과 같이 해야한다.

DP[현재 위치] = min( DP[현재 위치 + 1] + 트럭비용 * 현재 위치, (현재 위치 <= j <= 끝)DP[j + 1] + 헬리콥터 비용 + (i에서 j까지의 각각의 트럭 비용)))

즉, 현재 위치에서 트럭을 사용할 것인가, 아니면 특정 구간 내에 헬리콥터를 사용할 것인가? 를 결정하는 것이다.

 

헬리콥터로 이동할 위치는 해당 구간의 절반 위치가 타당하다. 왜냐하면, 구간 내 위치가 증가할때, 헬리콥터 위치에 따른 비용은 감소하다 다시 증가하는 양상을 띄는데, 절반의 위치가 그 중심점이 되기 때문이다.

이 위치를 중심점으로 잡았을 때, 이 위치보다 작은 왼쪽 구간과, 오른쪽 구간이 존재하는데, 중간에 부호가 바뀌기에 각 구간을 따로 계산해야한다.

 

그렇다면 이것을 어떻게 계산해야할까? 

- 왼쪽 구간 트럭 비용 = ((왼쪽 장소 갯수) * (중간 위치) - (왼쪽 위치 합)) * 트럭 비용

- 오른쪽 구간 트럭 비용 = ((오른쪽 위치 합) - (오른쪽 장소 갯수 * 중간 위치)) * 트럭 비용

이렇게 계산을 한다.

 

그렇게 나온 코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int N, dp[3001], P[3001], T, H, S[3001];
int solve(int idx)
{
	if (idx > N) return 0;
	int& ret = dp[idx];
	if (ret >= 0) return ret;
	ret = 1000000007;
	ret = min(ret, solve(idx + 1) + P[idx] * T);
	for (int i = idx; i <= N; i++)
	{
		int m = (idx + i) / 2;
		int l = ((m - idx + 1) * P[m]) - (S[m] - S[idx - 1]);
		int r = (S[i] - S[m]) - (P[m] * (i - m));
		ret = min(ret, solve(i + 1) + H + ((l + r) * T));
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> P[i];
	sort(P + 1, P + N + 1);
	for(int i = 1; i <= N; i++) 
		S[i] = S[i - 1] + P[i];
	cin >> T >> H;
	cout << solve(1) << '\n';
}

 

이 문제가 아쉬운게, 좀 더 생각을 해보면 떠올렸을 것 같은 아이디어인데, 괜히 구글링을 한 느낌이 든다.

아니면, 내가 장고시간을 너무 짧게 둔것일지도 모르겠다, 그래도 코딩 테스트에 대비하려면, 빨리빨리 아이디어를 제시해야하니 이런식으로 시간을 두는 연습을 해보자.

 

여담이지만, 이 문제는 정렬한 뒤에 부분 합을 구해야하는데, 버릇처럼 입력과 함께 부분합을 구해서 괜히 시간을 더 잡아먹었다. 이건 정말 고쳐야겠다.