글 읽기 - LCS2 코드 어느 부분에 문제가 있는지 궁금합니다 (주석 있음)

fpqpsxh 2년 전 0

DP로 문제를 풀던 중 알고리즘은 맞는 것 같은데 97% 구간에서 오답이 나옵니다.

string 배열을 활용하여 최대값을 알아내듯 최대문자를 저장하며 왔는데 어디서 오답이 발생하는지 도저히 모르겠습니다.

#include <bits/stdc++.h>
#define SETTING ios::sync_with_stdio(0), cin.tie(0)
using namespace std ;
string str1, str2 ;
string arr[2][1002] ;
int STRSIZE1, STRSIZE2 ;

void InputSetting()
{
    cin >> str2 >> str1 ;
    str1 = " " + str1, str2 = " " + str2 ;
    STRSIZE1 = str1.length() ;
    STRSIZE2 = str2.length() ;
}

void DP()
{
    //str1을 기준으로 str2에서 같은 문자가 나올 때마다 직전 str1 중 최대 문자열을 가져옴.
    //다른 문자열이 나온다면 직전 문자열 중 최대 길이를 가진 것을 가져옴
    for(int i = 1 ; i <= STRSIZE1 ; i++)
        for(int j = 1 ; j <= STRSIZE2 ; j++)
        {
            bool row = i % 2 ;
            if(str1[i] == str2[j]) arr[row][j] = arr[!row][j - 1] + str2[j] ;
            else arr[row][j - 1].length() >= arr[!row][j].length() ? arr[row][j] = arr[row][j - 1] : arr[row][j] = arr[!row][j] ;
        }
}

int main()
{
    SETTING ;
    InputSetting() ;
    DP() ;
    string it = arr[STRSIZE1 % 2][STRSIZE2] ;

    if(!it.empty())
        cout << it.length() - 1 << "\n" << it ;
    else
        cout << "0\n" ;
}

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

문제

문제

출처

ICPC

LCS2 코드 어느 부분에 문제가 있는지 궁금합니다 (주석 있음)

fpqpsxh 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말