boj 2216 문자열과 점수

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

 

같은 위치에 있는 문자를 비교하여 아래와 같이 점수를 받습니다.

1. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다.
2. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다.
3. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다.

 

여기서 문자 사이에 공백을 원하는대로 넣을수 있기 때문에

적절하게 공백을 넣어서 점수를 최대로 받아야 하는 문제입니다.

 

dp[idx1][idx2]: 문자열을 idx1, idx2까지 사용했을 때 얻을 수 있는 최대 점수

s1, s2 중 하나의 문자에 공백을 추가하거나 두 문자를 비교하여 a, b, c 중 적절한 값을 더합니다.

위 3가지 중 max를 구하도록 합니다.

 

 

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MAX 3010
using namespace std;
 
string s1, s2;
int dp[MAX][MAX];
int a, b, c;
int len1, len2;
 
int solve(int idx1, int idx2) {
    if (idx1 == len1) return (len2 - idx2) * b;
    if (idx2 == len2) return (len1 - idx1) * b;
 
    int& ret = dp[idx1][idx2];
    if (ret != -1) return ret;
    ret = b + max(solve(idx1 + 1, idx2), solve(idx1, idx2 + 1));
    if (s1[idx1] == s2[idx2]) {
        ret = max(ret, solve(idx1 + 1, idx2 + 1) + a);
    }
    else {
        ret = max(ret, solve(idx1 + 1, idx2 + 1) + c);
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0) << '\n';
}
 
void input() {
    cin >> a >> b >> c >> s1 >> s2;
    len1 = s1.size();
    len2 = s2.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}