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

풀이:

첫 번째 문자열을 : A

두 번째 문자열을 : B 라고 하자

먼저 위에 만들어진 표처럼 2차원 배열을 만들어 둔다.(초기 값들은 모두 0) 배열의 이름 : C

len(A) * len(B) 만큼 반복문을 돈다. (각 문자열이 일치하는지 확인하기 위해)

반복문을 돌며 A의 i번째 문자열과 B의 t번째 문자열이 일치한다면, C[i][t] = C[i - 1][t - 1] + 1 이다. 표에서 보면 왼쪽 대각선 값에서 + 1 을 해준 값이 된다.

만약 일치하지 않는다면, 배열의 위 값과 왼쪽 값 중 더 큰 것을 선택한다. 이렇게 선택함으로써 현재 위치에서 최대값을 갖게될 수 있다.

최종적으로는 배열의 오른쪽 끝에 값을 선택한다.

문자열을 찾기 위해서는 배열을 거꾸로 올라가면 된다.

대각선으로 증가했다면, 일치했다는 뜻이므로 대각선으로 증가한 부분만 선택하면 문자열을 찾을 수 있다.

코드:

사용언어 : python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

a,b=input(),input()
q,w=len(a)+1,len(b)+1
c,s=[[0]*q for _ in range(w)],''
for i in range(1,w):
    for t in range(1,q):
        if b[i-1]==a[t-1]:
            c[i][t]=c[i-1][t-1]+1
        else:
            c[i][t]=max(c[i][t-1],c[i-1][t])
print(c[-1][-1])
while i>0 and t>0:
    if c[i][t] == c[i-1][t]:    i-=1
    elif c[i][t] == c[i][t-1]:    t-=1
    else:   s+=a[t-1];i-=1;t-=1
print(s[::-1])