백준 24524 아름다운 문자열

https://www.acmicpc.net/problem/24524

• 문자열, 그리디 알고리즘

• 풀이
  문자열 S 에 대하여 반복해서 T를 찾으면 시간 초과가 날 수 있다고 생각했다.
  앞쪽 문자열이 이미 나왔는지를 확인한다. 만약 s[i]가 t[j]와 같을 시 t[j] 이전 문자들이 몇 번 나왔는지 확인한다. 이전 문자들이 더 적게 나왔을 경우 추가하지 않고 많이 나왔을 경우만 추가한다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long 
#define pii pair<long, long>

string s, t;
vector<int> A;
int cnt = 0;

bool check_prev(int N) {
	for (int i = 0; i < N; ++i) {
		if (!A[i] or A[i] <= A[N]) return false;
	}
	return true;
}

bool complete() {
	for (int i = 0; i < A.size(); ++i) {
		if (!A[i]) return false;
	}
	return true;
}

void del() {
	for (int i = 0; i < A.size(); ++i) A[i]--;
}

int main(void) {
	fast;

	cin >> s >> t;
	A.resize(t.size());
	for (int i = 0; i < s.size(); ++i) {
		for (int j = 0; j < t.size(); ++j) {
			if (s[i] == t[j]) {
				if (check_prev(j)) {
					A[j]++;
					if (complete()) {
						del(); cnt++;
					}
				}
			}
		}
	}
	cout << cnt;
}

• check_prev 함수 중 A[i] <= A[N] 부분을 추가해주셔야 합니다.
  재미있게 푼 문제입니다!