[BOJ/백준][Gold3] 2216 : 문자열과 점수 (C++)

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

2216번: 문자열과 점수

 

 

[난이도] Gold3
[유형] DP

[풀이]
DP[i][j] : 문자열 a를 i, b를 j부터 사용이 가능할 때, 공백을 추가해서 얻을 수 있는 점수의 최댓값
DP[i][j] = max (
B+DP[i+1][j] (a[i]만 추가하는 경우),
B+DP[i+1][j] (b[j]만 추가하는 경우),
DP[i+1][j+1] + a[i]==b[j] ? A : C (a[i]와 b[j] 모두 추가하는 경우, 같으면 A, 다르면 B)
)

 

#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int A,B,C,dp[3001][3001],inf=-1e9;
string s[2];
int sol(int n,int m){
    if(n==s[0].size()) return (s[1].size()-m)*B;
    if(m==s[1].size()) return (s[0].size()-n)*B;
    int& ret = dp[n][m];
    if(ret!=inf) return ret;
    ret = B+max(sol(n+1,m),sol(n,m+1));
    ret = max((s[0][n]==s[1][m] ? A : C) + sol(n+1,m+1),ret);
    return ret;
}
int main(){
    cin >> A >> B >> C >> s[0] >> s[1];
    for(int i=0;i<3000;i++) 
        for(int j=0;j<3000;j++) dp[i][j]=inf;
    cout << sol(0,0);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2216.cpp