[Python]동적계획법과 최단거리 역추적 백준 9252

 문제

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

LCS문제는 이전에 풀어봐서 그렇게 어렵지 않게 풀수 있었다.

문자열을 구하는것은 두가지 방법이있다.

이전에 했던것처럼 배열의 인자에 담아주는 방법과 역으로 추적하는 방법이 있다.

두가지 모두 구현해봐야겠다.

후자의 방법이 메모리 측면이나 시간측면에서도 훨씬 효율적일거같다.

import sys
S1=sys.stdin.readline().strip()
S2=sys.stdin.readline().strip()
 
 
 
DP=[[[0,""] for _ in range(len(S1)+1)] for _ in range(len(S2)+1)]
 
 
 
for i in range(1,len(S2)+1):#행
    for j in range(1,len(S1)+1):#열
        if S1[j-1]==S2[i-1]:#같은문자열을 발견하면
            DP[i][j][0]=DP[i-1][j-1][0]+1
            DP[i][j][1]=DP[i-1][j-1][1]+S2[i-1]
 
        else:#같은문자가 아니라면 위나 왼쪽중 더많은 문자열이 중복된곳을 따른다.
            if DP[i - 1][j][0] > DP[i][j - 1][0]:#왼쪽이크다면
                DP[i][j][0] = DP[i - 1][j][0]
                DP[i][j][1] = DP[i - 1][j][1]
            else:#위쪽이 크다면
                DP[i][j][0] = DP[i][j-1][0]
                DP[i][j][1] = DP[i][j-1][1]
 
print(DP[len(S2)][len(S1)][0])
for i in DP[len(S2)][len(S1)][1]:
    print(i,end="")

위와 같이 같은문자열을 만나서 DP의 값을 업데이트 시킬때 연속된 문자열도 같이 전달

하여 추가해 주었습니다.

DP=[[[0,""] for _ in range(len(S1)+1)] for _ in range(len(S2)+1)]

이부분을

DP=[[[0,[]] for _ in range(len(S1)+1)] for _ in range(len(S2)+1)] 로 작성하고 배열에 추가

하는형태로 구현하고 append 해줬을시 여러 문제가 발생하여 고생하였다.

사실 이 방법보다 아래 방법이 훨씬 효율적이다. 

먼저 DP를 통해 문자열수를 구하고 역으로 찾아가는 방법이다.

import sys
S1=sys.stdin.readline().strip()
S2=sys.stdin.readline().strip()
 
 
 
DP=[[0 for _ in range(len(S1)+1)] for _ in range(len(S2)+1)]
 
 
 
for i in range(1,len(S2)+1):#행
    for j in range(1,len(S1)+1):#열
        if S1[j-1]==S2[i-1]:#같은문자열을 발견하면
            DP[i][j]=DP[i-1][j-1]+1
 
        else:#같은문자가 아니라면 위나 왼쪽중 더많은 문자열이 중복된곳을 따른다.
            if DP[i - 1][j] > DP[i][j - 1]:#왼쪽이크다면
                DP[i][j] = DP[i - 1][j]
            else:#위쪽이 크다면
                DP[i][j] = DP[i][j-1]
 
 
print(DP[len(S2)][len(S1)])
result=[]
row=len(S2)#행
column=len(S1)#열
while column and row:#열이 0이 될때까지
    if DP[row][column]==DP[row-1][column]:#왼쪽과비교
        row-=1
 
    elif DP[row][column]==DP[row][column-1]:#위쪽과 비교
        column -= 1
 
    else: #대각선에서 왓을때
        result.append(S1[column - 1])
        column -= 1
        row -= 1
 
 
 
for i in range(len(result)-1,-1,-1):#반대로 출력
    print(result[i],end="")