白色光 2 (White Light 2)

작성일 | In

  • 문제 설명

    R,G,B 세 문자로 이루어진 문자열 $s$가 주어집니다. $A$원을 지불하면 앞 문자 하나를 삭제, $B$원을 지불하면 뒷 문자 하나를 삭제, $C$원을 사용하면 원하는 문자를 다른 문자로 변경 가능할 때 RGBRGB...RGB 꼴의 문자열을 만드는데 드는 최소 비용을 구하는 문제입니다.

  • 해설

    $dp[i][j]$를 $i$번째 문자를 $j$로 칠하려 할 때 드는 최소 비용이라고 정의합시다.
    우선 현재 칠해야 하는 색이 R, 즉 $j$가 $0$일 때, $b \times (n-i)$의 비용을 지불하고 그 부분부터 뒷 문자를 모두 삭제할 수 있습니다. 또 만약 $s[i] \neq j$라면 $dp[i][j] = min(dp[i][j], c + dp[i+1][(j+1)\% 3])$으로 전이할 수 있습니다.
    이후 모든 $0 \leq i \leq n$인 모든 $i$에 대해 $a\times i+dp[i][0]$의 최솟값을 구하면 답을 얻을 수 있습니다.

  • 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    ll n, a, b, c, s[200003];
ll dp[200003][3];
  
ll dfs(int id, int col) {
    ll& ret = dp[id][col];
    if(ret != -1) return ret;
    if(id == n) {
        if(col == 0) return ret = 0;
        else return ret = LLINF;
    }
    ret = LLINF;
    if(col == 0) ret = (n-id) * b;
    if(col == s[id]) {
        ret = min(ret, dfs(id+1, (col+1) % 3));
    } else {
        ret = min(ret, c + dfs(id+1, (col+1) % 3));
    }
    return ret;
}
  
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n;
    string t; cin >> t;
    for(int i=0; i<n; i++) {
        if(t[i] == 'R') s[i] = 0;
        else if(t[i] == 'G') s[i] = 1;
        else s[i] = 2;
    }
    cin >> a >> b >> c;
    ll ans = LLINF;
    for(int i=0; i<=n; i++) {
        ans = min(ans, i*a + dfs(i, 0));
    }
    cout << ans << '\n';
}