글 읽기 - 제 풀이에 어떤 문제가 있을까요?..

bansh123 3년 전 0

일단 제 아이디어는..

먼저 코돈 갯수가 M, DNA 서열 길이가 N이라 했을 때, 시작위치가 1~N일때 각 단백질이 만들어질 수 있는 DNA 서열상에서의 가장 왼쪽 위치를 구한 뒤, (없으면 -1) 2차원 행렬 (M*N) 에 저장해놓습니다.

그 후 1차원 행렬 (1*N)하나 만들어놓고 거기다가 DNA 길이 i까지 사용했을때 가능한 경우를 dp 방식으로 구한 뒤,

다 구하고 나서 전부 더해서 출력하는 식으로 생각을 했습니다.

서로다른 코돈이 같은 단백질에 대응하는 경우도 생각해서, 그 경우에는 그 코돈들을 다 생각했을 때 단백질이 만들어질 수 있는 가장 왼쪽의 위치만 포함하도록 했습니다.

하지만 어림도 없지, 제출하자마자 틀렸습니다가 뜨네요..

제 생각엔 이렇게하면 될 것 같은데.. 뭐가 틀렸을까요??

코드가 너무 가독성이 안 좋아서, 혹시 반례라도 주시면 너무 감사하겠습니다.

#include <iostream>
#include <string>
using namespace std;
int getloc(string DNA,string p, int idx, int size)
{
	int loc=-1;
	for (int i = 0; i < p.size(); i++)
	{
		bool t = 0;
		for (int j = idx; j < size; j++)
		{
			if (DNA[j] == p[i])
			{
				idx = j + 1;
				t = 1;
				break;
			}
		}
		if (t ==1 && i == p.size() - 1) 
		{
			loc = idx;
		}
		if (t == 0)
			break;
	}
	return loc;
}
int findnext(int* dp2, int i,int size)
{
	for (int a = i + 1; a < size; a++)
	{
		if (dp2[a] != 0)
			return a;
	}
	return size+1;
}
int main()
{
	int** dp;
	int * dp2;
	string DNA;
	cin >> DNA;
	int M;
	cin >> M;
	int size = DNA.size();
	dp = new int* [M];
	dp2 = new int[size+1];
	for (int i = 0; i < size+1; i++)
	{
		dp2[i] = 0;
	}
	for (int i = 0; i < M; i++)
		dp[i] = new int[size];
	for (int i = 0; i < M; i++)
		for (int j = 0; j < size; j++)
			dp[i][j] = -1;
	string* codonarr = new string[M];
	string* aminarr = new string[M];
	int* visited = new int[M];
	int* joongbok = new int[M];
	int** joongbokidx = new int*[M];
	for (int i = 0; i < M; i++)
	{
		visited[i] = i;
		joongbok[i] = 0;
		cin >> codonarr[i] >> aminarr[i];
	}
	for (int i = 0; i < M; i++)
	{
		for (int j = i + 1; j < M; j++)
		{
			if (visited[j] == j && aminarr[i].compare(aminarr[j]) == 0)
			{
				visited[j] = i;
				joongbok[i] += 1;
			}
		}
	}
	for (int i = 0; i < M; i++)
	{
		int s = joongbok[i] + 1;
		joongbokidx[i] = new int[s];
		int temp3 = 0;
		for (int k = 0; k < M; k++)
		{
			if (visited[k] == i)
			{
				joongbokidx[i][temp3++] = k;
			}
		}
	}
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < M; j++)
		{
			int idx = getloc(DNA, codonarr[j], i, size);
			dp[j][i] = idx;
		}
	}
	/*
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < size; j++)
		{
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	*/
	int size2 = (size)-2;
	for (int i = 0; i < size2; i=findnext(dp2,i,size))
	{
		for (int j = 0; j < M; j++)
		{
			if (visited[j] != j)
				continue;
			if (dp[j][i] == -1)
				continue;
			if (i == 0)
			{
				if (joongbok[j] == 0)
				{
					if (dp[j][i] > i + 2)
						dp2[dp[j][i]] += 1;
				}
				else
				{
					int temp = 9999;
					for (int k = 0; k <= joongbok[j]; k++)
					{
						if ((temp > dp[joongbokidx[j][k]][i]) && (dp[joongbokidx[j][k]][i] > i + 2))
						{
							temp = dp[joongbokidx[j][k]][i];
						}
					}
					dp2[temp] += 1;
				}
			}
			else
			{
				if (joongbok[j] == 0)
				{
					if (dp[j][i] > i + 2)
						dp2[dp[j][i]] += (dp2[i]);
				}
				else
				{
					int temp = 9999;
					for (int k = 0; k <= joongbok[j]; k++)
					{
						if ((temp > dp[joongbokidx[j][k]][i]) && (dp[joongbokidx[j][k]][i] > i + 2))
						{
							temp = dp[joongbokidx[j][k]][i];
						}
					}
					dp2[temp] += dp2[i];
				}
			}
		}
	}
	int res = 0;
	int div = 1000000007;
	/*
	for (int i = 0; i < size+1; i++)
	{
		cout << dp2[i]<< " ";
	}
	cout << endl;
	*/
	for (int i = 0; i < size+1; i++)
	{
		res += dp2[i] % div;
	}
	cout << res%div;
}

bansh123 3년 전 0

오버플로우 있는거 발견해서 단계마다 10억7로 나눠줘서 오버플로우 안나게 만들어주니까 이제 1프로에서 틀렸습니다네요 엌.

아무리 생각해도 모르겠어요 ㅠㅠ

bansh123 3년 전 0

흐어엉 117줄이 잘못됐었네요 겨우찾았습니다 흐허허ㅔㅎ

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

문제

문제

출처

ICPC

제 풀이에 어떤 문제가 있을까요?..

bansh123 3년 전 0

bansh123 3년 전 0

bansh123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말