[BOJ] 34984 간판 만들기

문제 요약

문제 링크: 백준 34894 - 간판 만들기

문제 설명

 

---

접근 방법

dp[i][j]

i: 현재 문자열 s의 i번째 인덱스까지 탐색했을 때,

j: 목표 문자열 "UOSPC"의 j번째 문자까지 완성하는 데 드는 최소 비용

 

최솟값을 구해야 하니, DP값을 모두 INF 값으로 초기화 해야 한다.

---

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
string s;
ll a[300001], dp[300001][5], ans = 1e14;
char x[5] = { 'U','O','S','P','C' };

void solve() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 5; j++)
            dp[i][j] = 1e13;
    }
    if (s[0] == 'U')  // 기저 사례
        dp[0][0] = a[0];
    for (int i = 1; i < n; i++) {
        if (s[i] == 'U')
            dp[i][0] = min(dp[i - 1][0], a[i]);
        else
            dp[i][0] = dp[i - 1][0];
        for (int j = 1; j < 5; j++) {
            if (s[i] == x[j])
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + a[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
        if (dp[i][4] != 1e13)
            ans = min(ans, dp[i][4]);
    }
    if (ans == 1e14) ans = -1;
    cout << ans;
}

void input() {
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> a[i];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}