글 읽기 - 2개를 비교하는거가 왜 틀린걸까요??

tega1996 2년 전 0

3개중 가장 짧은거 2개를 먼저 비교해서 LCS를 찾아서 그 배열을 만들고 그것을 다시 가장 긴 수열과 비교하면서 LCS의 길이를 찾으면 왜 틀릴까요?

질문에서 나온 반례들은 다 맞게 출력이되던데 어디서 틀린것일지 궁금합니다.

import sys

first = sys.stdin.readline().strip().upper()
second = sys.stdin.readline().strip().upper()
third = sys.stdin.readline().strip().upper()

if len(first) == min(len(first),len(second),len(third)):
    a = first
    if len(second) == min(len(second),len(third)):
        b,c = second,third
    else:
        c,b = second,third
elif len(second) == min(len(first),len(second),len(third)):
    a = second
    if len(first) == min(len(first),len(third)):
        b,c = first,third
    else:
        c,b = first,third
elif len(third) == min(len(first),len(second),len(third)):
    a = third
    if len(second) == min(len(first),len(second)):
        b,c = second,first
    else:
        c,b = second,first
            
result = [0]
for i in range(1,len(a)+1):
    for j in range(i,len(b)+1):
        if a[i-1] in b:
            result.append(a[i-1])
            break

matrix = [[0 for _ in range(len(result)+1)] for _ in range(len(third)+1)]

for i in range(1,len(third)+1):
    for j in range(1,len(result)+1):
        if third[i-1] == result[j-1]:
            matrix[i][j] = matrix[i-1][j-1] + 1
        else:
            matrix[i][j] = max(matrix[i-1][j],matrix[i][j-1])

print(matrix[-1][-1])

Green55 2년 전 1

일단 첫 두 LCS 구하는게 틀렸습니다. 35~40라인은 LSC를 제대로 구하신거 같은데, 27~31라인은 어떤 의도로 작성하신건지 잘 모르겠습니다.

또한 그걸 제대로 구해도, 첫 두 문자열에서 가능한 LCS가 여러개 있을 경우 어떤 걸 선택할지 결정할 수 없기 때문에, 본문에서 설명하신 방법도 틀렸습니다.

tega1996 2년 전 0

감사합니다 제가 생각이 짧았네요 다시 생각해보니까 접근방법에 오류가 조금 있었던 것 같습니다.

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

문제

문제

출처

ICPC

2개를 비교하는거가 왜 틀린걸까요??

tega1996 2년 전 0

Green55 2년 전 1

tega1996 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말