[백준] 9251 LCS (Python)

1. 문제 조건

• 첫째줄과 둘째 줄에 비교할 수열이 주어짐(각각의 길이는 같지 않을 수 있음)(최대 1000글자(알파벳 대문자))
• 문자열을 비교했을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것 찾기

 

2. 풀이 전 생각정리

• 수열 x와 y가 주어졌을 때 (x[0]과 y전부 비교하여 dp 갱신, x[1]과 y전부 비교하여 dp 갱신...) 이런 식으로 차근차근 dp를 갱신해보자
• dp의 크기는 (x의 길이+1) * (y의 길이+1) / 처음에는 다 0으로 채워넣어주기
• 이중 for문을 돌면서 두 가지 상황이 발생
  • x의 값과 y값이 같을 때
    • dp[i][j] = dp[i-1][j-1]+1
  • x의 값과 y값이 같지 않을 때
    • dp[i][j] = max(dp[i][j-1], dp[i-1][j])
• dp를 다 갱신하고 dp[-1][-1]을 출력하면 최종적으로 가장 긴 수열의 길이를 구할 수 있다.

 

3. 코드 구현

#두개의 문자열의 길이를 천천히 증가시켜보며 공통 부분 수열의 최대 길이를 갱신
#점화식 짜는게 중요(공집합 포함하여 추가)
x = input()
y = input()
dp = [[0]*(len(y)+1) for _ in range(len(x)+1)]

for i in range(1,len(x)+1): #x요소(i) 하나 당 y(j)를 전체 돌면서 갱신
    for j in range(1,len(y)+1):
        if x[i-1] == y[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
print(dp[-1][-1])