취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10168번 문제인 파발마이다.
문제는 아래 링크를 확인하자.

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

각 상소문은 시계방향으로만 움직이거나 반시계방향으로만 움직이는 것이 항상 최선임을 관찰하자. 또한 어떤 상소문을 시계방향으로 움직이는 경우, 그 상소문이 지나가게 되는 역에 있는 각 공문 또한 시계방향으로 움직이는 것이 항상 최선임을 관찰하자. 이는 반시계방향 움직임에도 마찬가지로 적용된다.

위의 관찰을 통해 어떤 한 도로를 기준으로 한 쪽의 상소문은 시계방향으로, 다른 쪽의 상소문은 반시계방향으로 공문들을 움직이는 경우 중 답이 항상 존재함을 알 수 있다.

역 i에서 시계방향/반시계방향으로 상소문을 움직이기로 결정했을 때의 그 경로에 있는 모든 역의 상소문을 옮기는 최소비용들을 각각 구할 수 있다면 이를 이용해 답이 최소가 되는 기준 도로를 찾아내는 것으로 문제를 해결할 수 있다. 이 값들을 dp를 이용해 해결해보자.

역 $n$에서부터 반시계방향에 존재하는 모든 역의 상소문을 (반시계방향으로) 한양까지 옮기는 최소비용을 $dp[n]$이라 하자. 이 때, 다음과 같은 점화식을 세울 수 있다. (단, $S_m$은 한m번 역에서 한양까지의 옮겨야 할 상소문의 개수이다.)

$dp[n]=min(dp[k]+(S_n-S_k)n)(k<n)$

이와 같은 점화식을 그대로 구현하면 $O(N^2)$의 시간복잡도로 문제를 해결할 수 있다. 이는 서브태스크 4를 통과하기에 불충분한 시간복잡도이다.

위의 점화식의 우변을 다음과 같이 정리해보자.

$dp[n]=min(-S_{k}n+dp[k])+S_{n}n(k<n)$

이 때 min 안의 식은 $k$를 상수로 생각했을 때 n을 변수로 갖는 일차함수의 식으로 생각할 수 있다. 또한 $-S_k$는 단조감소하므로 $n$은 단조증가하므로 $N$ 이하의 각 $n$에 대한 모든 $dp$값은 $O(N)$ CHT를 이용해 구할 수 있다. (글쓴이는 $O(NlgN)$ 시간복잡도로 해결하였다.)

위의 방법은 시계방향으로 공문을 이동시킬 때에도 적용 가능하다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

ll N;
ll arr[1000001];
deque<pll> dq;
ll total = 0;

ll func(int idx, ll x) {
	return dq[idx].first * x + dq[idx].second;
}

ll CHT1(ll x) {
	int L = 0, R = dq.size() - 1;
	while (L < R) {
		int mid1 = (L + R) / 2;
		int mid2 = mid1 + 1;
		if (func(mid1, x) > func(mid2, x)) L = mid2;
		else R = mid1;
	}

	ll p = dq[L].first, q = dq[L].second;
	return p * x + q;
}

void CHT2(ll a, ll b) {
	while (dq.size() > 1) {
		int idx1 = dq.size() - 1, idx2 = dq.size() - 2;
		ll p1 = dq[idx1].first, q1 = dq[idx1].second;
		ll p2 = dq[idx2].first, q2 = dq[idx2].second;

		if ((q2 - b) * (a - p1) < (q1 - b) * (a - p2)) break;
		dq.pop_back();
	}
	dq.push_back(make_pair(a, b));
}

ll dp1[1000002];
ll dp2[1000002];
ll ans = 1000000000000000007LL;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (ll n = 1; n <= N; n++) cin >> arr[n];

	dq.push_back(make_pair(0, 0));
	for (ll n = 1; n <= N; n++) {
		if (arr[n]) {
			total++;
			dp1[n] = CHT1(n) + (total + 1) * n;
			
			CHT2(-total, dp1[n]);
		}
		else dp1[n] = dp1[n - 1];
	}

	total = 0;
	dq.clear();
	dq.push_back(make_pair(0, 0));
	for (int n = N; n > 0; n--) {
		if (arr[n]) {
			total++;
			dp2[n] = CHT1(N - n + 1) + (total + 1) * (N - n + 1);

			CHT2(-total, dp2[n]);
		}
		else dp2[n] = dp2[n + 1];
	}
	
	for (int i = 1; i < N; i++) ans = min(ans, dp1[i] + dp2[i + 1]);

	cout << ans;
}