백준4243 보안 업체

작성일 | In

문제 링크

  • http://icpc.me/4243

문제 출처

  • 2013 대전 리저널 인터넷 예선 K번

사용 알고리즘

  • DP

시간복잡도

  • O(N2)

풀이

2315 가로등 끄기문제처럼 왼쪽/오른쪽, 양 방향으로 하나씩 dp table을 채워나가는 느낌으로 답을 구해줍니다.

dp[s][e] = [s, e]구간을 이미 탐색했을 때, 전체를 탐색하기 위해 추가로 소요되는 시간 으로 정의를 하려고 하는데, 한 가지 파라미터를 더 추가해야 합니다.
명우가 [s, e]구간을 순찰을 완료하고 나서 s에 있을수도 있고, e에 있을수도 있습니다. flag라는 파라미터를 만들어서 s에 있다면 0, e에 있다면 1로 잡아줍시다.

[s, e]구간을 순찰했다면, [1, s) 구간과 (e, N]구간은 순찰을 안 한 상태입니다.
위치 사이의 거리를 빠르게 구하기 위해 prefix sum을 만들어 순찰할 구역의 위치에 대한 누적합을 만들어줍시다.

  • remain = 순찰을 하지 않은 구간의 개수 = n - e + s - 1
  • now = 현재 위치 = flag ? e : s
  • sum[x] = prefix sum

처럼 정의한다면 점화식은 아래와 같이 채울 수 있습니다.

  • (1 < s) : dp[s][e] = f(s-1, e, 0) + remain * (sum[now] - sum[s - 1]) -> 왼쪽으로 이동
  • (e < N) : dp[s][e] = f(s, e+1, 1) + remain * (sum[e + 1] - sum[now]) -> 오른쪽으로 이동

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;

ll dp[111][111][2];
vector<ll> sum;
int n;

ll f(int l, int r, int flag) {
	ll &res = dp[l][r][flag];
	if (res != -1) return res;
	if (l == 1 && r == n) return res = 0;
	res = 1e18;
	ll now = flag ? r : l;
	ll remain = n - r + l - 1;
	if (1 < l) res = min(res, f(l - 1, r, 0) + remain * (sum[now] - sum[l - 1]));
	if (r < n) res = min(res, f(l, r + 1, 1) + remain * (sum[r + 1] - sum[now]));
	return res;
}

void solve(){
	memset(dp, -1, sizeof dp);
	sum.clear();
	cin >> n; sum.resize(n + 1);
	int start; cin >> start;
	for (int i = 2; i <= n; i++){
		cin >> sum[i];
		sum[i] += sum[i - 1];
	}

	cout << min(f(start, start, 0), f(start, start, 1)) << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) solve();
}