글 읽기 - LCS 문제에서 왜 틀리는지 모르겠네요 ㅠ 변수 타입도 고쳤는데...

wwiiiii 10년 전 1

일단 예제 데이터부터 하나 적게 나오네요; 뭐가 문젠지...

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[1010][1010];//dp[str1][str2]

int main()
{
	char str1[1010];
    char str2[1010];
    int str1_len , str2_len;
    scanf("%s %s",str1,str2);
    str1_len = strlen(str1);
    str2_len = strlen(str2);
    for(int i=0;i<str1_len;i++)
    {
    	if(str1[i]==str2[0])dp[i][0] = 1;
    }
    for(int i=0;i<str2_len;i++)
    {
    	if(str2[i]==str1[0])dp[0][i] = 1;
    }
    for(int i=1;i<str1_len;i++)
    {
    	for(int j=1;j<str2_len;j++)
        {
            if(str1[i] == str2[j]) {dp[i][j] = dp[i-1][j-1] + 1;}
            else {dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}
        }
    }
    printf("%d",dp[str1_len-1][str2_len-1]);
    return 0;
}

WeissBlume 10년 전 1

if(str1[i]==str2[0])dp[i][0] = 1;

else dp[i][0] = dp[i-1][0]

이런 식으로 else가 추가돼야 할 것 같네요

wwiiiii 10년 전 1

아...앞에 있는걸 기저에서 고려 안했네요 ㅠㅠ 감사합니다!

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

문제

문제

출처

ICPC

LCS 문제에서 왜 틀리는지 모르겠네요 ㅠ 변수 타입도 고쳤는데...

wwiiiii 10년 전 1

WeissBlume 10년 전 1

wwiiiii 10년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말