글 읽기 - DP이거 왜틀렸나요??

qkqhxla1 6년 전 0

RRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

이게 16억인가 나오던데.. 제 코드는 적게 나옵니다. 어떤 경우를 빼먹은걸까요??

#include <iostream>
#include <string>
using namespace std;

string scroll, bridge[2];
int dp[2][105];

int go(int i,int j,int index)
{
	if(j>bridge[0].length() || index > scroll.length()-1)
		return 0;
	else if(index==scroll.length()-1)
	{
		if (bridge[i][j]==scroll[index])
			return 1;
		return 0;
	}
	int &ret = dp[i][j];
	if(ret!=0) return ret;

	for(int k=j+1;k<bridge[0].length() - (scroll.length() - (index+1)) + 1;k++)
		if(bridge[!i][k]==scroll[index+1])
			ret += go(!i,k,index+1);
	return ret;
}

int main()
{
	cin>>scroll;
	cin>>bridge[0]>>bridge[1];
	int answer = 0;
	for(int i=0;i<2;i++)
		for(int j=0;j<bridge[0].length()-scroll.length()+1;j++)
			if(bridge[i][j]==scroll[0])
				answer += go(i,j,0);
	cout<<answer<<endl;
	return 0;
}

skysign 3년 전 0

저는 3차원 DP로 풀었는대, 아래 풀이 영상 참고해보세요.

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

문제

문제

출처

ICPC

DP이거 왜틀렸나요??

qkqhxla1 6년 전 0

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말