[백준] 2216번 - 문자열과 점수[C++]

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

2216번: 문자열과 점수

 

안녕하세요 오늘도 DP 문제로 돌아왔습니다

 

1. 문제

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

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

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

a	' '	b	c
' '	d	' '	c

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

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

 

2. 풀이

한번의 계산에는 세가지 경우의 수가 존재합니다.

1. 둘 다 문자를 고르는 경우(점수는 두가지 경우가 있음).

2. 첫 문자열에서는 문자, 두번째 문자열에서는 공백을 고르는 경우.

3. 첫 문자열에서는 공백, 두번째 문자열에서는 문자를 고르는 경우.

 

따라서 Score[i][j]를 첫번째 문자열 i번째 문자, 두번째 문자열 j번째 문자까지 왔을 때의 최대 점수라고 한다면(아직 문자를 사용하지 않은)

1. Score[i-1][j-1] + (A or C)(i-1번째 문자와 j-1번째 문자가 같다면 A, 다르다면 C)

2. Score[i-1][j] + B

3. Score[i][j-1] + B

중 최대값이 Score[i][j]가 되겠습니다.

 

3. 코드

Bottom-up 방식입니다.

dp[i][j]의 의미는 위 Score[i][j]와 동일하게 i번째 문자, j번째 문자까지 왔을 때의 최대 점수입니다.

문자열은 0번째 부터 시작하기 때문에 위 예시에 따르면 최종 정답은 a, b, c를 모두 소모하고 d, c를 모두 소모한 후인

최종 정답은 dp[3][2]가 되겠습니다.(dp[2][1]이 아님을 주의)

//https://www.acmicpc.net/problem/2216
//2216. 문자열과 점수(Gold 3, DP)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long

using namespace std;

int N;
string str1, str2;
int str1_len, str2_len;
ll dp[3001][3001];
int A, B, C;
ll ans = -LL_INF;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> A >> B >> C;
    cin >> str1 >> str2;

    //SOLVE
    str1_len = str1.length(), str2_len = str2.length();
    for(int i = 0; i < 3001; i++) {
        for(int j = 0; j < 3001; j++) {
            dp[i][j] = -LL_INF;
        }
    }

    dp[0][0] = 0;
    for(int i = 0; i < str1_len + 1; i++) {
        for(int j = 0; j < str2_len + 1; j++) {
            if(i > 0 && j > 0) {
                int tscore = (str1[i-1] == str2[j-1]) ? A : C;
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + tscore);
            }
            if(j > 0) {
                dp[i][j] = max(dp[i][j], dp[i][j-1] + B);
            }
            if(i > 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j] + B);
            }
        }
    }
    
    //OUTPUT
    cout << dp[str1_len][str2_len];
}

 

아래는 Top-down 방식입니다.

ll cal(int idx1, int idx2) {
    if(idx1 == str1_len && idx2 == str2_len) return 0;
    
    ll &ret = dp[idx1][idx2];
    if(ret != -LL_INF) return ret;

    ret = -LL_INF;
    ll score;

    //둘 다 문자 선택
    if(idx1 < str1_len && idx2 < str2_len) {
        score = (str1[idx1] == str2[idx2]) ? A : C;
        ret = max(ret, score + cal(idx1+1, idx2+1));
    }

    //str1은 문자, str2는 공백 선택
    score = B;
    if(idx1 < str1_len) ret = max(ret, score + cal(idx1+1, idx2));

    //str1은 공백, str2는 문자 선택
    score = B;
    if(idx2 < str2_len) ret = max(ret, score + cal(idx1, idx2+1));

    return ret;
}

//cout << cal(0, 0)

 

부족한 글 읽어주셔서 감사합니다. 지적, 질문 모두 환영입니다.

오늘 하루 웃음이 가득하시길~!!