문제
문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.
이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.
입력
첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.
출력
첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.
코드
str1 = input()
str2 = input()
str3 = input()
dist = [[[0]*(len(str3)+1) for _ in range(len(str2)+1)]
for _ in range(len(str1)+1)]
for i in range(1, len(str1)+1):
for j in range(1, len(str2)+1):
for k in range(1, len(str3)+1):
if str1[i-1] == str2[j-1] and str2[j-1] == str3[k-1]:
dist[i][j][k] = max(dist[i][j][k], dist[i-1][j-1][k-1] + 1)
else:
dist[i][j][k] = max(dist[i-1][j][k], dist[i]
[j-1][k], dist[i][j][k-1])
print(dist[len(str1)][len(str2)][len(str3)])
2개의 문자열로 LCS를 만들 때와 크게 다르지 않다고 생각했다. 그래서 LCS의 길이를 저장할 3차원 배열 dist를 만들고 다이나믹 프로그래밍을 이용하여 dist 배열의 값을 채웠다.
입력으로 주어진 문자열을 각각 str1, str2, str3라고 한다.
- 각 문자열의 인덱스를 i, j, k라고 했을때 str1[i] = str2[j] = str3[k]가 되는 순간이 LCS의 길이가 길어질 수 있는 순간이다. 그러므로 이 때 dist[i][j][k]에 저장되어 있는 값보다 dist[i-1][j-1][k-1]+1이 더 크다면 dist[i][j][k] = dist[i-1][j-1][k-1]+1로 갱신해준다.
- 만약 str1[i], str2[j], str3[k] 셋 중 하나라도 같지 않다면 dist[i][j][k] 값은 dist[i-1][j][k], dist[i][j-1][k], dist[i][j][k-1] 중 최대 값으로 바꿔준다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 17484번 진우의 달 여행 (Small) (0) | 2024.02.04 |
---|---|
[Python/파이썬] 백준 13302번 리조트 (0) | 2024.01.23 |
[Python/파이썬] 백준 11060번 점프 점프 (0) | 2023.12.25 |
[Python/파이썬] 백준 1309번 동물원 (1) | 2023.12.02 |
[Python/파이썬] 백준 1535번 안녕 (0) | 2023.11.30 |