[백준/BOJ] 백준 12019번 : 동아리방 청소!

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

12019번: 동아리방 청소!

날짜, 청소할 수 있는 횟수, 이전에 청소한 날짜를 고려한 다이나믹 프로그래밍을 통해 문제를 해결했다. vector<int> dirty_sum(101, 0); 에 누적합을 구하는 방식으로 [날짜] = 더러움 (청소를 안 한다고 했을 때)를 저장하여 이전에 청소한 날짜를 알았을 때 현재 불쾌함을 구할 수 있도록 했다.((dirty_sum[here] - dirty_sum[before_clean + 1]) * person[here]) 그리고 언제 청소를 할지 구하는 방법은 cache에 저장된 값을 이용하여 현재 장소를 청소하는게 청소를 하지 않는 것보다 손해보진 않을 때 청소하는 방식으로 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector<int> person(101);
vector<int> dirty_sum(101, 0); //[날짜] = 더러움 (청소를 안한다고 했을때)
vector<int> result;
int cache[101][11][101];

void Pre()
{
	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 11; j++)
			for (int k = 0; k < 101; k++)
				cache[i][j][k] = -1;
}

//here : 날짜, can_clean : 청소할 수 있는 횟수, before_clean : 이전에 청소한 날짜
int Solve1(int here, int can_clean, int before_clean)
{
	if (here > n)
		return 0;

	int& ret = cache[here][can_clean][before_clean];

	if (ret != -1)
		return ret;

	//불쾌함
	ret = (dirty_sum[here] - dirty_sum[before_clean + 1]) * person[here];

	//청소를 할 수 있을때
	if (can_clean > 0)
	{
		//현재 장소를 청소하는것과 청소하지 않는것중 더 불쾌함이 작은 값을 구한다
		ret += min(Solve1(here + 1, can_clean - 1, here), Solve1(here + 1, can_clean, before_clean));
	}

	//청소를 할 수 없을때
	else
	{
		ret += Solve1(here + 1, can_clean, before_clean);
	}

	return ret;
}

//here : 날짜, can_clean : 청소할 수 있는 횟수, before_clean : 이전에 청소한 날짜
void Solve2(int here, int can_clean, int before_clean)
{
	//청소가 끝났을때
	if (can_clean == 0)
		return;

	//현재 장소를 청소하는게 청소를 하지 않는것보다 손해보진 않을때
	if (cache[here + 1][can_clean - 1][here] <= cache[here + 1][can_clean][before_clean])
	{
		result.push_back(here);

		Solve2(here + 1, can_clean - 1, here);
	}

	else
	{
		Solve2(here + 1, can_clean, before_clean);
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		person[i] = input;
		dirty_sum[i + 1] = dirty_sum[i] + input;
	}

	cout << Solve1(1, m, 0) << "\n";

	Solve2(1, m, 0);

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";

	return 0;
}