백준 22886, Moons and Umbrellas

개요

문제 링크
골드 5, DP, Greedy
CJ 또는 JC가 나타날 때마다 X,Y의 비용을 지불할 때 비용의 최솟값 구하기

---

접근

1. DP의 정석같은 문제, 끝이 C, J일때를 기준으로 DP를 돌리면 된다.
2. 만약 현재 끝이 J라면 min(이전J, 이전C+CJ), 끝이 C라면 min(이전C, 이전J+JC)를 해주면 된다. 끝이 ?라면 각각 C, J일때에 대해 각각 생각해주면 된다.
3. 문제가 헷갈리는 부분은 두가지인데, 문제를 그리디하게 생각해버리면서 생긴다. 그런데 완탐을 해도 문제가 없고 그리디로 생각하면 한없이 복잡해진다.
   1. 먼저 x나 y가 양수라는 가정하에는 C만 계속 연속되거나 J만 계속 연속되는 것이 이득이라 생각할 수 있다. 그래서 그리디로 접근할 수 있는데 그럴 필요가 없다.
   2. CJ또는 JC를 번갈아서 놓으면 최대라고 생각할 수 있는데 또한 그럴 필요가 없다. dp배열을 잘 만들어주면 굳이 최적의 선택을 고려할 필요가 없는 것이다.

---

Pseudo code

if (s[i] = 'C')
    dp[i].C = min(dp[i-1].C, dp[i-1].J + JC);
    dp[i].J = MAX
else if (s[i] = 'J')
    dp[i].C = MAX
    dp[i].J = min(dp[i-1].J, dp[i-1].C + CJ);
else
    dp[i].C = min(dp[i-1].C, dp[i-1].J + JC);
    dp[i].J = min(dp[i-1].J, dp[i-1].C + CJ);

---

Source code

#include <bits/stdc++.h>
using namespace std;
using str = string;
using vec = vector<int>;
void test() {
    int x, y;
    str s;
    cin >> x >> y >> s;
    vec dp(2, 2e9);
    if (s[0] != 'J') dp[0] = 0;
    if (s[0] != 'C') dp[1] = 0;
    for (int i = 1; i < s.size(); i++) {
        int c = dp[0], j = dp[1];
        dp[0] = dp[1] = 2e9;
        if (s[i] != 'J')
            dp[0] = min(c, j + y);
        if (s[i] != 'C')
            dp[1] = min(j, c + x);
    }
    cout << min(dp[0], dp[1]) << "\n";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        test();
    }
}