PS/BOJ

[BOJ] 백준 12019. 동아리방 청소! (Gold I)

kth990303 2021. 8. 15. 19:57
반응형

문제

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

 

12019번: 동아리방 청소!

첫째 줄에는 N일 까지의 각 사람들이 느낀 불쾌함의 총합의 최솟값을 출력하고 두 번째 줄에는 그 때 청소한 날짜를 오름차순으로 출력한다. 정답이 여러 가지인 경우에는 사전 순으로 앞서는

www.acmicpc.net

알고리즘이 뭔지 파악하기 쉽게 생겨서 무난할 줄 알았는데,

청소한 날짜를 출력하는 부분에서 조금 애를 먹었던 문제.

 

오늘은 이 문제를 포스팅하려 한다.


의식의 흐름 및 해설

N, M이 굉장히 작다.

시간초과 걱정은 뒤로 미뤄두어도 괜찮을 듯하다.

우선 청소를 언제 할지에 따라 답이 굉장히 다양해지므로 브루트포스 알고리즘이나 DP를 생각할 수 있겠다.

 

이런 형태의 DP문제를 많이 풀어와서 그런지, 나는 DP로 접근하였다.

처음 접근한 dp 점화식은 dp[cur][cnt]=dp[cur-1][cnt-1]+dp[cur-1][cnt], cur번째 날까지 cnt번 청소했을 때 불쾌함의 총합이었다.

 

그렇게 식을 짜고 코드를 작성했는데, 생각해보니 cur번째까지의 더러움이 얼마인지 알아야 불쾌함의 총량을 구할 수 있기 때문에 점화식에 더러움의 양을 추가하였다. 시간을 줄이기 위한 방법으로 누적합 방식이 있을 듯하나, 나는 그냥 인자에 전달하는 방식을 이용했다. 그렇게 해도 어차피 O(N^2*M) 정도이기 때문이다.

 

여기까진 무난하게 식을 짜서 답을 도출했다.

문제는 dp 역추적이다. 

이 역추적 코드를 짜는데에는 문제의 힌트가 많은 도움이 됐다.

역추적 방법에는 여러 가지가 있는데, 하나는 현재 점화식과 이전 점화식의 값이 같을 때 그 이전 점화식으로 계속 나아가는 방식으로 추적을 하는 것이고, 다른 하나는 dp식 과정에서 따로 값을 저장해서 추적하는 것이다. (둘이 결국 똑같은거긴 하다...)

 

나는 전자의 방법을 사용하였다.

역추적 코드를 짤 때는 위에 작성한 dp 점화식을 참고하여 이전점화식 그대로 작성해주면 된다.

난 주로 탑다운 dp를 쓰므로 이전점화식이 아닌, 재귀dp점화식 그대로 쓰면 된다.

 

아래 dp 점화식을 역추적하려면,

ret = dp(cur + 1, n + a[cur], cnt) + n * a[cur];
if (cnt < M)
	ret = min(ret, dp(cur + 1, a[cur], cnt + 1));

아래와 같이 작성하면 되는 것이다.

	if (d[i + 1][n + a[i]][cnt] + n*a[i]>= d[i + 1][a[i]][cnt + 1]) {
		n = a[i];
		cout << i << " ";
		cnt++;
	}
	else
		n += a[i];

위의 dp 점화식과 그대로인데,

그 이유는 재귀dp는 바텀업dp와 순서가 반대이기 때문이다.


코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
const int MAX = 101;
const int INF = 0x3f3f3f3f;
int N, M, a[MAX], d[MAX][2001][11];
vector<int> ans;
int dp(int cur, int n, int cnt) {
	if (N - cur < M - cnt)
		return INF;
	if (cur >= N)
		return cnt == M ? 0 : INF;
	int& ret = d[cur][n][cnt];
	if (ret != -1)
		return ret;
	ret = dp(cur + 1, n + a[cur], cnt) + n * a[cur];
	if (cnt < M)
		ret = min(ret, dp(cur + 1, a[cur], cnt + 1));
	return ret;
}
void trace(int n, int cnt) {
	for (int i = 0; i < N; i++) {
		if (cnt == M)
			break;
		if (d[i + 1][n + a[i]][cnt] + n*a[i]>= d[i + 1][a[i]][cnt + 1]) {
			n = a[i];
			cout << i << " ";
			cnt++;
		}
		else
			n += a[i];
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	memset(d, -1, sizeof(d));
	cout << dp(0, 0, 0) << "\n";
	trace(0, 0);
}

오랜만에 DP 역추적 문제를 풀었더니 기빨려버렸다...

역추적은 항상 볼때마다 무서운듯.

반응형