백준 7346 유전자 함수

https://boj.ma/7346/t

7346번: 유전자 함수

 

주어지는 두 유전자 문자열의 길이를 같게 적절히 공백을 추가했을 때 얻어지는 결괏값의 최대치를 알고 싶습니다.

또한 같은 위치에 두 문자열 모두에 공백이 있으면 안 됩니다.

주어지는 문자열의 길이는 100을 넘지 않습니다.

 

완전탐색부터 생각해 보면

문자열 두 개를 만들건대 문자열 각각의 인덱스를 n, m이라고 하면 첫 번째 문자열의 n번째 위치에 공백을 넣거나, 두 번째 문자열의 m번째 위치에 공백을 넣거나, 두 문자열 모두에 공백을 넣지 않거나

3가지 경우에 대해 분기를 나누어 진행하면 답을 찾을 수 있을 것 같습니다.

하지만 모든 경우에 대해 해 본다면 시간초과입니다.

 

예제의 문자열을 그대로 들고 왔습니다.

AGTGATG
GTTAG

 

 

첫 번째 문자열의 3번 인덱스까지 만들었고,  두 번째 문자열의 2번 인덱스까지 만들었을 때 그 이후에 공백을 적절히 채워 최댓값을 찾는 것은 이전에 어떤 방식으로 공백을 채웠든 항상 일정할 것입니다.

따라서 dp로 최적화가 가능합니다.

 

코드(c++)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define NM 101010
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 100000000
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;


int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    vector<vector<int>> arr = {
            {5, -1, -2, -1, -3},
            {-1, 5, -3, -2, -4},
            {-2, -3, 5, -2, -2},
            {-1, -2, -2, 5, -1},
            {-3, -4, -2, -1, 0}
    };
    string s = "ACGT*";
    map<char, map<char, int>> mp;

    for(int i = 0; i < 5 ;i ++){
        for (int j = 0 ; j < 5; j++){
            mp[s[i]][s[j]] = arr[i][j];
        }
    }

    int t;
    cin >> t;
    while(t--){
        int n, m;
        string s1, s2;
        cin >> n >> s1 >> m >> s2;
        if (n < m) swap(n, m), swap(s1, s2);
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
        auto recur = [&](const auto&self, int a, int b) -> int{
            if (a == n){
                int total = 0;
                for (int i = b ;i < m; i++){
                    total += mp['*'][s2[i]];
                }
                return total;
            }
            if (b == m){
                int total = 0;
                for (int i = a ;i < n; i++){
                    total += mp[s1[i]]['*'];
                }
                return total;
            }
            int&ret = dp[a][b];
            if (ret != -1) return ret;
            ret = -INF;
            // 두개를 직접 비교
            ret = max(ret, self(self, a + 1, b + 1) + mp[s1[a]][s2[b]]);
            // s1을 공백으로 채운다
            ret = max(ret, self(self, a, b + 1) + mp['*'][s2[b]]);
            // s2를 공백으로 채운다
            ret = max(ret, self(self, a + 1, b) + mp[s1[a]]['*']);
            return ret;
        };

        cout << recur(recur, 0,0 ) << endl;

    }


    return 0;
}

 

약간 귀찮은 전처리만 해주면 됩니다