BOJ-12019 동아리방 청소!

필요한 지식

1. 동적계획법

접근

최소 더러움 구하기

• dp[i][j][k] : i번째 날, j번의 청소남음, 마지막청소했던 날 k 로 dp테이블을 구성했다.

• arr[i] : i번째 날 방문하는 사람 수

• 재귀로 끝까지 내려갔다고 올라오면서 답을 내는 방식으로 구현했다.

• go(now,cnt,state,dust) : now번째 날 cnt번의 청소가 남았고, state는 마지막청소를 했던날, dust는 현재 불쾌함이다.

• ret 에 먼저 청소를 하지않고 다음날로 진행하는 값을 넣어주고, 청소를 할수 있다면(cnt>0), 현재 ret값과 청소를 했을 경우의 값을 비교해 더 작은 값을 넣어준다.

ret = go(now + 1, cnt, state, dust + arr[now]);
if (cnt > 0) ret = min(ret, go(now + 1, cnt - 1, now, 0));

• 그 후 오늘의 불쾌함(arr[now] * dust)을 더해준 후 반환한다.

청소한 날짜 추적하기

• 추적하는 문제를 언제 풀어봤는지 기억도 안난다. 처음 풀어본거 같기도하고..

• traceback(cnt,state)함수가 최소 더러움을 뽑아낸 경우를 추적한다.

• for문에서 i는 날짜를 의미하고 현재날짜에서 청소를 안한경우(dp[i + 1][cnt][state])와 한경우(dp[i + 1][cnt - 1][i])를 비교해 주고 더 작은 값을 가지는 곳으로 따라간다.

• 청소한 날짜를 사전 순으로 출력해야 하므로 청소를 안 했을 때 와 했을 때 값이 같다면 청소를 한 경우로 따라가 주어야 한다.

코드(C++)

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n, m, x;
int arr[102], dp[102][12][102];
int go(int now, int cnt, int state, int dust) {
	if (now == n + 1) return 0;
	int& ret = dp[now][cnt][state];
	if (ret != -1) return ret;

	ret = go(now + 1, cnt, state, dust + arr[now]);
	if (cnt > 0) ret = min(ret, go(now + 1, cnt - 1, now, 0));

	return ret += arr[now] * dust;
}
void traceback(int cnt, int state) {
	for (int i = 1; i < n; i++) {
		if (!cnt) break;
		if (dp[i + 1][cnt][state] >= dp[i + 1][cnt - 1][i]) {
			state = i;
			cout << i << " ";
			cnt -= 1;
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> x;  arr[i] = x;
	}
	cout << go(1, m, 0, 0) << "\n";
	traceback(m, 0);
	return 0;
}

---

결과