BOJ 11994 - Circular Barn Revisited (dp)

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

dp식은 대충짜지 말자고 다짐한 문제

 

<문제설명>

최대 100개의 칸으로 나뉜 원형 헛간이 있다. 각 칸마다 외부로 통하는 문이 있고 양 옆 칸으로 이동하는 문이 있다. 외부에서 내부로 통하는 문을 지나는데는 비용이 들지 않는다. 옆 칸으로 이동할 때 반드시 시계방향으로 움직여야 하고 지나간 문의 수의 제곱만큼의 비용이 든다.

현재는 소들이 모두 외부에 있고, 최대 k개의 외부 문을 열어서 각 칸에 소가 정확히 ri마리씩 들어가도록 하고 싶다. 이 때 최소 비용을 구해라.

 

<풀이> ... (구간합 때문에 1base로 구현함)

당연히 시계방향 기준으로 뒤에 있는 소가 앞에 있는 소를 추월하는 것은 최적이 아니다.

 

0번 문을 처음으로 열어 줄 때~ n-1번 문을 처음으로 열어 줄 때 상황 중 최소비용을 구할 것이다. 배열의 크기를 두배로 늘려서 계산을 편하도록 조정했다.

 

dp[s][t]

 : s번 문을 처음으로 열어준다고 할 때 s번 칸부터 s+n-1칸까지 앞으로 문을 열 기회가 t번 있을 때 최소 비용

 

sum(s,e)

 : 소들이 외부에서 s번칸으로 진입하여 e번칸까지 자리잡는데 드는 비용

위와 같이 구간합 두개로 O(1)에 구할 수 있다.

 

 

sum을 이용해서 dp점화식을 세우면 다음과 같다. (끝점은 항상 s+n-1임에 주의)

 

 

 

정답은 dp[1][k]~dp[n-1][k] 중 최소값이다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
typedef long long ll;
const int MAX = 1e3 + 2;
const ll IMP = 2e18;

ll n, k, dp[MAX * 2][8], a[MAX * 2], ps[MAX * 2], ps2[MAX * 2];
bool chk[MAX * 2][8];

inline ll sum(int s, int e) {
	return ps2[e] - ps2[s] - (s) * (ps[e] - ps[s]);
}

ll f(int s, int t, const int e) {
	if (t == 0) return sum(s, e);

	ll& ret = dp[s][t];
	if (chk[s][t]) return ret;
	chk[s][t] = true;
	ret = sum(s, e);

	for (int m = s; m < e; m++)
		ret = min(ret, sum(s, m) + f(m + 1, t - 1, e));

	return ret;
}

int main() {
	FAST;
	cin >> n >> k;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
		ps[i] = ps[i - 1] + a[i];
		ps2[i] = ps2[i - 1] + i * a[i];
	}
	for (ll i = n + 1; i <= 2 * n; i++) {
		a[i] = a[i - n];
		ps[i] = ps[i - 1] + a[i];
		ps2[i] = ps2[i - 1] + i * a[i];
	}

	ll ans = IMP;
	for (int i = 1; i < n; i++) {
		memset(chk, 0, sizeof(chk));
		ans = min(ans, f(i,k - 1,i + n - 1));
	}

	cout << ans << '\n';
}

 

<생각>

dp점화식이 확실하게 나올 때까지 재귀식 세우는건 지양해야겠다. 한번 잘못 꽂히면 벗어나질 못하겠다.