7346번: 유전자 함수
boj.ma
주어지는 두 유전자 문자열의 길이를 같게 적절히 공백을 추가했을 때 얻어지는 결괏값의 최대치를 알고 싶습니다.
또한 같은 위치에 두 문자열 모두에 공백이 있으면 안 됩니다.
주어지는 문자열의 길이는 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;
}
약간 귀찮은 전처리만 해주면 됩니다
'알고리즘 문제 풀이' 카테고리의 다른 글
| 백준 2001 보석 줍기 (2) | 2024.08.31 |
|---|---|
| 백준 17943 도미노 예측 (0) | 2024.07.18 |
| 백준 23889 돌 굴러가유 (0) | 2024.05.16 |
| 백준 31786 최고의 친구 (0) | 2024.05.09 |
| 백준 31782 저체온증 (0) | 2024.05.02 |
