[ boj : 21941 ] 문자열 제거

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

21941번: 문자열 제거

해설 : 전형적인 dp 문제입니다. 

 

len 을 문자열 s의 길이라고 정의를 합시다.

 

dp[i] = 인덱스 i 부터 len-1 까지 제거했을때 가장 최대로 얻을 수 있는 점수

 

라고 점화식을 세워보죠.

 

현재 위치한 알파벳으로 시작하는 지울 수 있는 문자열이 존재한다면 그 문자열과 완전히 일치하는지 검사를 하고 일치하면 함수로 들어가고, 아니면 그냥 문자 하나만 지우던지 선택지는 2개입니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

string s;
int m;
vector<string> v[30];
map<string, int> mp;
int dp[1010];

int f(int x);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string x;
	int y;
	cin >> s >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		mp[x] = y;
		v[x[0] - 'a'].push_back(x);
	}
	memset(dp, -1, sizeof(dp));
	cout<<f(0);
	return 0;
}
int f(int x)
{
	if (x == s.length())return 0;
	if (x > s.length())return -1;
	int& ret = dp[x];
	if (ret != -1)return ret;

	ret = 0;
	for (string str : v[s[x] - 'a'])
		if(str==s.substr(x,str.length()))
			ret = max(ret, f(x + str.length()) + mp[str]);
	ret = max(ret, f(x + 1) + 1);
	return ret;
}