청소하는 날을 골라 사람들이 느끼는 불쾌함을 최소로 하여 값을 출력하고 청소하는 날을 출력하는 문제입니다.
완전 탐색으로 접근하면 N 일 중에 M 번을 청소하는 날을 중복되지 않게 고르고 최솟값과 청소한 날을 출력하면 됩니다.
하지만 모든 경우를 보게 되면 O(\(_NC_M\))이므로 제한 시간을 초과하게 됩니다.
그래서 시간을 줄여야 하는데 이런 문제는 보통 DP 문제가 많기 때문에 DP로 접근을 했습니다.
DP에 저장할 때 필요한 정보가 총 일수, X 번째 일에 불쾌함의 최소를 저장하려고 합니다.
하지만 그것만으로는 정확한 답을 얻을 수가 없으니
청소를 할 수 있는 날이 며칠이 남았는지, 전에 청소한 날짜를 추가하도록 하겠습니다.
DP[날짜][남은 청소 횟수][전에 청소한 날짜] = 불쾌함의 총합의 최솟값
탑다운 방식으로 구현을 했고 날짜 - now, 남은 청소 횟수 - cnt, 전에 청소한 날짜 - pre, arr - 당일 인원수로 설명하겠습니다.
남은 청소 횟수, 즉 청소할 수 있는 날이 더 있을 때는 그날 청소를 했을 때와 청소를 하지 않았을 때를 비교하여 최솟값을 저장합니다.
그 최솟값에 현재 불쾌함을 더해주면 불쾌함의 합의 최솟값을 저장할 수 있습니다.
DP[now][cnt][pre] = min(DP[now+1][cnt-1][now], DP[now+1][cnt][pre]) + sum * arr[now]
DP[now+1][cnt-1][now] - 청소를 하여 cnt가 하나 줄고, 최근 청소를 한 날짜를 now로 바꿔줍니다.
DP[now+1][cnt][pre] - 청소를 하지 않아 cnt, pre가 그대로입니다.
남은 청소 횟수가 없을 때는 청소를 할 수 없기 때문에 DP[now+1][cnt][pre]만 계산하여 대입하면 됩니다.
DP[now][cnt][pre] = DP[now+1][cnt][pre] + sum * arr[now]
저렇게 구하다가 (now == N)이 되면 청소를 해도 다음날이 없어 하거나 안 하거나 상관이 없기 때문에 현재 불쾌함을 저장하여 반환해 주면 됩니다.
불쾌함을 저장할 때는 현재 더러움을 저장하는 재귀 함수 변수로 sum이라는 변수를 추가했습니다.
청소를 했을 때 sum = 0으로 청소를 하지 않았을 때는 (sum + arr[now])를 구해주면 됩니다.
불쾌함은 현재 더러움 * 당일 인원 수이므로 (now==N) 일 때 (sum * arr[now])를 하여 현재 불쾌함을 저장 후 반환해 줍니다.
기저 사례도 정했으니 재귀 함수를 실행하면 DP 배열에 원하는 값들이 저장되어 있습니다.
DP[1][m][0]에 저희가 원하는 답이 들어있어 출력하시면 됩니다.
하지만 아직 청소한 날짜를 출력을 해야 합니다.
이를 하기 위해 DP 배열을 이용하여 역추적을 하겠습니다.
DP 배열을 완성하는 과정을 따라가면서 DP 배열에 들어있는 값에 따라 청소 날짜를 구할 수 있습니다.
일단 DP[1][m][0]에 불쾌함의 합의 최솟값이 들어있기 때문에 시작을 now = 1, cnt = m, pre = 0으로 시작하겠습니다.
DP[now][cnt][pre]을 저장하기 위해 DP[now + 1][cnt][pre], DP[now + 1][cnt - 1][now]를 비교하여 둘 중 최솟값을 저장했습니다.
둘을 비교하여 최솟값을 저장했기 때문에 둘을 비교하여 더 작은 쪽을 따라가면 됩니다.
DP[now + 1][cnt][pre]이 더 작으면 청소를 하지 않은 것이고, DP[now + 1][cnt - 1][now]이 더 작으면 청소를 한 것입니다.
그래서 now 일에 청소를 했다면 cnt–, pre = now을 하여 다음 청소한 날을 구해주시면 되고 now를 출력해 주시면 됩니다.
정답이 여러 가지 일 때 사전 순으로 출력하라고 했으니 now를 1~N 순서대로 봐서 두 개의 값이 같을 때는 청소를 했다고 해야 사전 순으로 출력을 할 수 있습니다.
다른 분들이 푼 풀이 중에 DP[N][M]으로 DP 배열을 구성하신 분들도 있던데 이 풀이를 생각해내기 아직 부족한 것 같네요… ㅠ
DP 문제를 요즘 풀어보면서 DP 배열을 이용한 역추적 문제를 조금씩 풀고 있는데 풀다 보니까
재밌는 것 같기도 하고… 음…….
흠…… 크흠…..
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main() {
FIO;
int n, m; cin >> n >> m;
int arr[101], dp[101][11][101];
memset(dp, -1, sizeof(dp));
FOR(i, 1, n) cin >> arr[i];
function <int(int, int, int, int)> DP = [&](int now, int cnt, int pre, int sum) {
int& ret = dp[now][cnt][pre];
if (ret != -1) return ret;
if (now == n) return ret = sum * arr[now];
ret = 1e9;
if (cnt) ret = min(ret, DP(now + 1, cnt - 1, now, 0));
ret = min(ret, DP(now + 1, cnt, pre, sum + arr[now]));
return ret += arr[now] * sum;
};
auto trace = [&]() {
int cnt = m, pre = 0;
FOR(i, 1, n - 1) {
if (!cnt) break;
int a = dp[i + 1][cnt][pre], b = dp[i + 1][cnt - 1][i];
if (a >= b) pre = i, cnt--, cout << i << ' ';
}
};
cout << DP(1, m, 0, 0) << '\n';
trace();
return 0;
}