03/03 PS 문제풀이

작성일 | In

1099 - 알 수 없는 문장(G3)

[문제 링크]

길이 $N(1\leq N\leq50)$의 문자열 $S$이 주어지고, 주어진 부분 문자열 $M(1\leq M\leq 50)$개를 적절히 이어붙여 $S$를 만들어야 합니다. 한 부분 문자열 $T$에서는 문자의 순서를 임의로 바꿀 수 있으며, 그 비용은 원래 $T$와 일치하지 않는 문자의 갯수만큼 듭니다. 이 비용을 최소화 하는 것이 문제입니다.

$dp[i]$를 $i$번째 문자부터 끝까지 완성시키는데 최소 비용이라고 정의한 뒤 모든 부분문자열 $T$를 시도해보면 됩니다.

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
string s;
int n, dp[51];
vector<string> a;

int dfs(int id) {
    int& ret = dp[id];
    if(ret != -1) return ret;
    if(id == sz(s)) return ret = 0;
    ret = INF;
    for(int i=0; i<n; i++) if(id + sz(a[i]) <= sz(s)) {
        vector<int> cnt(26);
        for(int j=id,k=0; j<id + sz(a[i]); j++,k++) {
            cnt[s[j]-'a']++;
            cnt[a[i][k]-'a']--;
        } 
        int suc = 1;
        for(int j=0; j<26; j++) if(cnt[j]) suc = 0;
        if(!suc) continue;
        int score = 0;
        for(int j=id,k=0; j<id + sz(a[i]); j++,k++) {
            if(s[j] != a[i][k]) {
                score++;
            }
        } 
        ret = min(ret, score + dfs(id + sz(a[i])));
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> s >> n;
    a = vector<string>(n);
    for(int i=0; i<n; i++) cin >> a[i];
    cout << (dfs(0)==INF?-1:dfs(0)) << '\n';
}

17234 - Scoring Hack(G2)

[문제 링크]

0점에서 시작해서 매 턴마다 다음과 같이 행동할 수 있습니다 : $a$점을 얻거나, $b$점을 얻거나, 현재까지 턴의 수의 10% 이하로 점수를 2배 뻥튀기 할 수 있습니다. $n$점 이상 $n+a$점 이하 점수를 얻을 수 있는 최소 턴을 구하면 됩니다. 단순한 BFS로 [현재 점수, 현재 턴수, 2배 뻥튀기 횟수] 상태를 관리하면서 최솟값을 구할 수 있습니다.

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
38
39
int vis[601][501][11];

struct state {
    int score, turn, sp; 
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, a, b; cin >> n >> a >> b;
    memset(vis, 0x3f, sizeof vis);
    queue<state> q;
    q.push({0, 0, 0}); 
    vis[0][0][0] = 0;
    while(sz(q)) {
        int sc = q.front().score;
        int tu = q.front().turn;
        int sp = q.front().sp; q.pop();
        if(sc >= n + a) continue;
        if(sc >= n) {
            cout << vis[sc][tu][sp] << '\n';
            return 0;
        }
        // win 
        if(sc+a <= n+a && vis[sc+a][tu+1][sp] == INF) {
            vis[sc+a][tu+1][sp] = vis[sc][tu][sp] + 1;
            q.push({sc+a, tu+1, sp});
        } 
        // lose
        if(sc+b <= n+a && vis[sc+b][tu+1][sp] == INF) {
            vis[sc+b][tu+1][sp] = vis[sc][tu][sp] + 1;
            q.push({sc+b, tu+1, sp});
        }
        // double
        if(sc*2 <= n+a && tu+1 >= 10 * (sp+1) && vis[sc*2][tu+1][sp+1] == INF) {
            vis[sc*2][tu+1][sp+1] = vis[sc][tu][sp] + 1;
            q.push({sc*2, tu+1, sp+1});
        }
     }
}

16399 - 드라이브(P5)

[문제 링크]

길이 $D$ 도로 위 주유소가 위치 $L_1, L_2, \cdots, L_N$에 있고, 각 주유소마다 기름 가격은 $P_1, P_2, \cdots, P_N$입니다. 기름 용량이 $C$, 연비가 $E\ell/km$인 차가 $0$에서 출발하여 $D$ 지점까지 갈 때 최소한의 주유 비용으로 $D$​에 도달하는 비용을 구하면 됩니다. (처음에는 기름이 가득 있습니다.) 찾아보니 문제 태그가 dp 이외엔 없을 정도로 dp 풀이가 많던데, greedy한 방법으로 문제를 풀 수 있어서 소개합니다.

다음과 같은 greedy한 방법으로 기름을 채우면 됩니다. 자신의 위치보다 기름값이 적은 첫 오른쪽 위치를 $X$라고 합시다. 만약 현재 가지고 있는 기름으로 $X$까지 도달 가능하다면, 이동합니다. 그렇지 않다면, $X$까지 겨우 도달할 수 있을 정도의 최소 기름을 넣고 갑니다. $X$를 넘어갈 정도로 기름을 채우게 된다면, $X$에서 기름을 사는 것이 더 이득이기 때문에 정당성을 부여할 수 있습니다. 모든 주유소 위치에서의 $X$는 뒤에서부터 monotone stack을 유지하면서 구해내면 $O(N)$에 구할 수 있습니다.

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
38
39
40
41
42
43
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int c, e, d; cin >> c >> e >> d;
    int n; cin >> n;
    vector<pii> a(n+2);
    int cur = 0;
    for(int i=1; i<=n; i++) {
        int s; cin >> s;
        cur += s;
        if(s * e > c) {
            cout << -1 << '\n';
            return 0;
        }
        a[i].ff = cur;
    }
    if((d - cur) * e > c) {
        cout << -1 << '\n';
        return 0;
    }
    a[n+1].ff = d;
    for(int i=1; i<=n; i++) {
        cin >> a[i].ss;
    }
    stack<pii> st;
    vector<int> rht(n+2);
    st.push({d, 0});
    for(int i=n; i>=1; i--) {
        while(st.top().ss > a[i].ss) st.pop();
        rht[i] = st.top().ff;
        st.push({a[i].ff, a[i].ss});
    }
    int curOil = c - a[1].ff * e;
    int ans = 0;
    for(int i=1; i<=n; i++) {
        int curDis = a[i].ff;
        int nxtDis = rht[i];
        int needOil = min(c, (nxtDis - curDis) * e);
        ans += max(0, (needOil - curOil) * a[i].ss);
        curOil = max(curOil, needOil);
        curOil -= e * (a[i+1].ff - a[i].ff); 
    }
    cout << ans << '\n';
}