글 읽기 - 어디가 잘못된 걸까요

paranocean 5년 전 0

DP배열 역추적을 하지 않고 어떻게든 배열 이중 참조를 통해 풀고 싶은데, 어떻게 고쳐야 할지 잘 모르겠네요. 예제도 제대로 나오지 않아요. 어디가 잘못되었는지 조언을 부탁합니다..

#include <stdio.h>
#include <string.h>

char A[1001];
char B[1001];
int LCS[1001][1001];
char string[1001][1001]; //string[i]=길이가 i인 LCS

int max(int a, int b) {return a>b ? a:b;}

int main(void)
{
  scanf("%s%s",A,B);
  int LenA=strlen(A);
  int LenB=strlen(B);

  for (int i=0; i<LenA; i++)
    for (int j=0; j<LenB; j++)
      if (A[i]==B[j])
      {
        LCS[i+1][j+1]=LCS[i][j]+1;
        strcpy(string[LCS[i+1][j+1]], string[LCS[i][j]]);
        char tmp[2]={A[i], '\0'};
        strcat(string[LCS[i+1][j+1]], tmp);
      }
      else
        LCS[i+1][j+1]=max(LCS[i][j+1], LCS[i+1][j]);

  printf("%d\n%s",LCS[LenA][LenB], string[LCS[LenA][LenB]]);
}

djm03178 5년 전 1

길이가 x인 LCS는 여럿 있을 수 있습니다. 하지만 길이가 x인 모든 LCS에서 길이가 x+1인 LCS를 만들 수 있는 것은 아닙니다. 그래서 길이가 x+1인 LCS를 만들려면 경로를 정확하게 따라온 그 길이가 x인 LCS에다가 A[i]를 덧붙여야지, 다른 경로로 온 LCS에 A[i]를 덧붙이면 깨지게 됩니다.

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

문제

문제

출처

ICPC

어디가 잘못된 걸까요

paranocean 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말