[백준9252] LCS 2

https://www.acmicpc.net/problem/9252

 

 

 

문제 해결 방법

1. dp배열을 만들어서 lcs를 구함

2. lcs를 구한 dp배열을 역추적하여 문자열을 구함 

 

코드 구현

정답 코드 

 

s1 = input()
s2 = input()

m=len(s1)
n=len(s2)

dp = [[0] * (n+1) for _ in range(m+1)]

for i in range(1, m+1):
    for j in range(1, n+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i][j-1], dp[i-1][j])

result =''
startm = m
startn = n

print(max(dp[-1]))
if max(dp[-1])!=0:
    while 1:
            if dp[startm][startn]==0:
                break
            # 위에것이 더 큰지
            if dp[startm][startn] == dp[startm-1][startn]:
                startm-=1
            # 왼쪽 것이 더 큰지
            elif dp[startm][startn] == dp[startm][startn-1]:
                startn-=1
            # 둘다 안크면 대각선 이동 
            # 값도 넣어줌 
            elif ((dp[startm][startn]-1) == dp[startm-1][startn-1]):
                
                startm-=1
                startn-=1

                result+=s2[startn]


            
            

    print(result[::-1])

 

시간/공간 복잡도

0.1초로 시간제한이 있었는데, 해당 시간에 1000만 번의 연산을 해야하는거고, 최대로 입력할 수 있는 문자열의 길이가 1000이기 때문에 

O(n)으로 푸는것이 맞다. 

 

최적화 및 개선

따로 하지 않음 

 

어려웠던 점

lcs의 개념, lcs의 역추적의 개념을 잘 몰라서 접근하기 어려웠다. 

역추적 부분은 아직도 어렵게 느껴진다. 비슷한 문제를 여러번 풀어봐야 할 것 같다.