백준 문제 풀이
LCS 최장 공통 부분 수열 : 3개일 때 길이 뿐만 아니라, 부분문자열까지 찾아내기 @@황소처럼 우직하게@@
hjp845
2020. 2. 20. 16:31
반응형
백준 1958 파이썬 python : LCS 3 @@황소처럼 우직하게@@
처음엔 아래 코드와 같이, a b c 의 lcs 는 (a b 의 lcs) 와 (c) 의 lcs 이겠지 생각했으나 틀렸다. def lcs(a, b): dp = [[0 for i in range(len(a) + 1)] for j in range(len(b) + 1)] for i in range(1, len(b)..
hjp845.tistory.com
이전 글에서 길이를 찾아내는 문제를 풀어보았다.
이번에는 부분문자열까지 찾아내는 솔루션을 제시한다.
이런 문제가 사이트에 있을진 모르겠지만, 충분히 나올 수 있는 문제다.
lst = [input() for i in range(3)]
dp = [[[0 for i in range(len(lst[0]) + 1)] for j in range(len(lst[1]) + 1)] for k in range(len(lst[2]) + 1)]
for k in range(1, len(lst[2]) + 1):
for j in range(1, len(lst[1]) + 1):
for i in range(1, len(lst[0]) + 1):
if lst[0][i - 1] == lst[1][j - 1] == lst[2][k - 1]:
dp[k][j][i] = dp[k - 1][j - 1][i - 1] + 1
else:
dp[k][j][i] = max(dp[k - 1][j][i], dp[k][j - 1][i], dp[k][j][i - 1], dp[k - 1][j - 1][i], dp[k][j - 1][i - 1], dp[k - 1][j][i - 1])
ans = ''
now = dp[-1][-1][-1]
k = len(dp) - 1
j = len(dp[0]) - 1
i = len(dp[0][0]) - 1
while now != 0:
if now - 1 == dp[k - 1][j][i] == dp[k][j - 1][i] == dp[k][j][i - 1] == dp[k - 1][j - 1][i] == dp[k][j - 1][i - 1] == dp[k - 1][j][i - 1]:
ans = lst[0][i - 1] + ans
k -= 1
j -= 1
i -= 1
now -= 1
else:
flag = []
value = 0
if dp[k - 1][j][i] > value:
value = dp[k - 1][j][i]
flag = [k - 1, j, i]
if dp[k][j - 1][i] > value:
value = dp[k][j - 1][i]
flag = [k, j - 1, i]
if dp[k][j][i - 1] > value:
value = dp[k][j][i - 1]
flag = [k, j, i - 1]
if dp[k - 1][j - 1][i] > value:
value = dp[k - 1][j - 1][i]
flag = [k - 1, j - 1, i]
if dp[k - 1][j][i - 1] > value:
value = dp[k - 1][j][i - 1]
flag = [k - 1, j, i - 1]
if dp[k][j - 1][i - 1] > value:
value = dp[k][j - 1][i - 1]
flag = [k, j - 1, i - 1]
k, j, i = flag
print(dp[-1][-1][-1])
print(ans)알고리즘은 간단하다
주변 6개 칸이 현재칸 값보다 다 1씩 낮다면, 현재 문자열을 ans에 추가한다. 그리고 i - 1, j - 1, k - 1 칸으로 이동한다.
그렇지 않다면
주변 6개 칸중에서 큰 값을 찾고 그 칸으로 이동한다.
0이 되면 탐색을 종료한다.
반복문으로 깔끔하게 풀 수도 있었으나, 6개정도니 그냥 if문 6개로 풀었다.
반응형