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

2216번 : 문자열과 점수

---

문제)

알파벳 소문자로 구성된 길이 1 이상의 두 문자열 X, Y가 있다. 이 문자열들의 임의의 위치에 공백을 삽입하여 두 문자열의 길이를 같게 만든 다음, 앞에서부터 한 글자씩 살펴보면서, 같은 위치에 있는 두 문자 X[i], Y[i]에 대해서 다음과 같이 점수를 계산한다.

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

예를 들어 A = 10, B = -1, C = -5인 경우, 다음과 같은 경우들을 살펴보자.

 

 

이 경우 앞에서부터 점수를 계산하면 각각 -1, -1, -1, 10점이 되고 따라서 총점은 7점이 된다.

두 문자열이 주어졌을 때, 공백을 적절히 추가했을 때 얻을 수 있는 최대 총점을 구하는 프로그램을 작성하시오.

 

 

입력 :

첫째 줄에 세 정수 A, B, C (0 < A ≤ 10,000, -10,000 ≤ B, C < 0) 가 주어진다. 그리고 둘째 줄에 X가, 셋째 줄에 Y가 주어진다. 각 문자열의 길이는 3,000자를 넘지 않으며 빈 문자열은 입력으로 주어지지 않는다.

 

 

 

출력 :

첫째 줄에 최대 총점을 출력한다.

 

 

 

 

 

 

풀이)

 

// 2216. 문자열과 점수
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int a, b, c;
string X, Y;
 
int dp[3010][3010];
 
int recur(int x, int y)
{
    // b, c가 음수이기 때문에 매우 작은 값을 설정한다.
    if (x > X.length() || y > Y.length()) return -9999999;
    if (x == X.length() && y == Y.length()) return 0;
    
    if (dp[x][y] != -1) return dp[x][y];
 
    int ret = -10000000;
 
    // 1. 두 문자가 서로 같은 경우
    if (X[x] == Y[y]) ret = max(ret, recur(x + 1, y + 1) + a);
 
    // 2. 두 문자 중 적어도 하나가 공백인 경우
    ret = max(ret, recur(x + 1, y) + b);
    ret = max(ret, recur(x, y + 1) + b);
 
    // 3. 두 문자가 모두 공백이 아니고 서로 다른 경우
    if (X[x] != Y[y]) ret = max(ret, recur(x + 1, y + 1) + c);
 
    dp[x][y] = ret;
 
    return ret;
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> a >> b >> c >> X >> Y;
    
    fill(&dp[0][0], &dp[3009][3010], -1);
 
    cout << recur(0, 0);
 
    return 0;
}

---

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

2216번: 문자열과 점수