문제
https://www.acmicpc.net/problem/12019
알고리즘이 뭔지 파악하기 쉽게 생겨서 무난할 줄 알았는데,
청소한 날짜를 출력하는 부분에서 조금 애를 먹었던 문제.
오늘은 이 문제를 포스팅하려 한다.
의식의 흐름 및 해설
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 역추적 문제를 풀었더니 기빨려버렸다...
역추적은 항상 볼때마다 무서운듯.
'PS > BOJ' 카테고리의 다른 글
[BOJ] 백준 22876. 츠바메가에시 (Platinum IV) (0) | 2021.08.26 |
---|---|
[BOJ] 백준 10165. 버스 노선 (Platinum V) (0) | 2021.08.26 |
[BOJ] 백준 2517. 달리기 (Platinum IV) (0) | 2021.08.06 |
[BOJ] 백준 21923. 곡예 비행 (Gold IV) 탑다운 DP (0) | 2021.08.01 |
[BOJ] 백준 22358. 스키장 (Gold II) (0) | 2021.08.01 |