BOJ 24524 : 아름다운 문자열

• 문제 링크 : boj.kr/24524
• 난이도 : G5
• 태그 : 그리디

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    string s, t;
    cin >> s >> t;
    map<char, int> idx;
    for(int i = 0; i < t.size(); i++) {
        idx[t[i]] = i+1;
    }
    vector<int> cnt(t.size()+1, 0);
    cnt[0] = INF;

    for(int i = 0; i < s.size(); i++) {
        int curr = idx[s[i]];
        if(curr == 0) continue;
        if(cnt[curr] < cnt[curr-1]) cnt[curr] += 1;
    }
    cout << cnt[t.size()];

    return 0;
}

---

풀이

문자를 만들 수 있는 대로 만들어본다.

S의 왼쪽부터 한 문자씩 나에게 블록으로 주어진다고 생각해 보자.

이 블록을 아래의 판에 내려놓을 수 있는지를 판단할 것이다. 만약 이 블록을 내려놓아 T의 [0,K] 부분 문자열을 만들 수 있다면 블록을 내려놓는다. 즉 이미 완성된 부분 문자열의 뒤에 붙일 수 있다면 내려놓는다.

이렇게 블록을 내려놓으며 최종적으로 완성된 T의 수를 세면 된다.