글 읽기 - 2306 질문입니다.

chatterboy 8년 전 0

c(i,j) = [i,j]에서 제거할 유전자의 최소 갯수라 하고 풀었습니다.

c(i,J) = c(i+1, j-1), if (dna[i] = 'a' and dna[j] = 't') or (dna[i] = 'g' and dna[j] = 'c')

c(i,j) = min{c(i+1,j)+1, c(i,j-1)+1, c(i,k) + c(k+1,j)} k = [i+1, j) otherwise

TLE인데 어떻게 줄일 수 있나요?

그리고 O(n^3)인줄 알았는데 반복적으로 바꾸는 과정에서 적어도 O(n^4)이 나오던데 잘 이해가 안되네요 ㅠ

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, dp[505][505];
char dna[505];
int solve(int l, int r) {
	if (l >= r) return l == r ? 1 : 0;
	int &ret = dp[l][r];
	if (ret != -1) return ret;
	if ((dna[l] == 'a' && dna[r] == 't') ||
		(dna[l] == 'g' && dna[r] == 'c'))
		return ret = solve(l+1, r-1);
	else {
		int ret = 1 + min(solve(l+1, r), solve(l, r-1));
		for (int k = l+1; k+1 < r; k++)
			ret = min(ret, solve(l, k) + solve(k+1, r));
		return ret;
	}
}
int main() {
	memset(dp, -1, sizeof(dp));
	scanf("%s", dna + 1);
	n = strlen(dna + 1);
	printf("%d", n - solve(1, n));
}

portableangel 8년 전 1

케이스분류를 살살 해보시면 g가 가장 가까운 c와 매칭되었을 때만 체크해도(뒤쪽에 더 나오는 c를 무시해도) 최대값을 구할 수 있다는 것을 알 수가 있습니다.

모든 g,c / a,t pair에 대해 재귀호출을 하지 않고 각 g에서 오른쪽으로 가장 가까운 c, 각 a에서 오른쪽으로 가장 가까운 t 하나로만 재귀호출을 하게 바꾸시면 통과가 될거예요

chatterboy 8년 전 0

@portableangel

그렇군요~ 신기하네요

답변 감사합니다

jsjsjs0775 3년 전 0

구현하기 따라 다르군여

저는 a, t // g,c 각각을 가장 큰 길이를 찾도록 했어요

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
string str;

int dp[500][500];

int dfs(int s, int e) {

	if (s < 0 || e >= str.length()) return 0;
	if (s >= e) return 0;
	if (dp[s][e] != -1) return dp[s][e];
	int& ret = dp[s][e] = 0;


	for (int i = s; i < e; i++) {

		if (str[i] == 'a') {

			int as, ae, L;

			for (int j = e; j > i; j--) {

				if (str[j] == 't') {

					as = i; ae = j;
					ret = max(ret, 2 + dfs(s, as - 1) + dfs(as + 1, ae - 1) + dfs(ae + 1, e));
					break;
				}
			}
		}
	}
	for (int i = s; i < e; i++) {

		if (str[i] == 'g') {

			int as, ae;

			for (int j = e; j > i; j--) {

				if (str[j] == 'c') {

					as = i; ae = j;
					ret = max(ret, 2 + dfs(s, as - 1) + dfs(as + 1, ae - 1) + dfs(ae + 1, e));
					break;
				}
			}
		}
	}
	//cout << s << " " << e << " ret:" << ret << "\n";
	return ret;
}

int main(void)
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(dp, -1, sizeof(dp));
	cin >> str;
	cout << dfs(0, str.length() - 1);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2306 질문입니다.

chatterboy 8년 전 0

portableangel 8년 전 1

chatterboy 8년 전 0

jsjsjs0775 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말