[G5] 백준 9251 - LCS (python3)

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

9251번: LCS

---

해결방법

2차원 배열의 캐시값을 만들어 해결했다.

- 백준 사이트의 [예제 입력 1]
      A  C  A  Y  K  P  
  [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 1, 1, 2, 2, 2, 2]
P [0, 1, 1, 2, 2, 2, 3]
C [0, 1, 2, 2, 2, 2, 3]
A [0, 1, 2, 3, 3, 3, 3]
K [0, 1, 2, 3, 3, 4, 4]

- 백준 사이트 질문글에 있는 반례
      A  C  A  A  
  [0, 0, 0, 0, 0]
A [0, 1, 1, 1, 1]
A [0, 1, 1, 2, 2]
A [0, 1, 1, 2, 3]
C [0, 1, 2, 2, 3]
B [0, 1, 2, 2, 3]
A [0, 1, 2, 3, 3]

여기를 누르면 해당 질문글로 이동합니다.

풀이👀

1. 두 문자열을 순회한다.

2-1. 일치하는 문자이면, 왼쪽 대각선 위의 수+1을 한 값을 지금 위치에 저장한다.

2-2. 일치하는 문자가 아니면, 바로 왼쪽과 바로 위쪽 숫자 중 더 큰 값을 지금 위치에 저장한다.

 

아래 더보기를 누르면 예제입력1을 풀이하는 순서를 간략하게 볼 수 있습니다. (사지방이라 이게 최선입니다 ㅠ)

1
      A  C  A  Y  K  P  
  [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 0, 0, 0, 0, 0, 0]
P [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 0, 0, 0, 0, 0]
A [0, 0, 0, 0, 0, 0, 0]
K [0, 0, 0, 0, 0, 0, 0]
==============
2
      A  C  A  Y  K  P  
  [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 1, 1, 2, 2, 2, 2]
P [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 0, 0, 0, 0, 0]
A [0, 0, 0, 0, 0, 0, 0]
K [0, 0, 0, 0, 0, 0, 0]
==============
3
      A  C  A  Y  K  P  
  [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 1, 1, 2, 2, 2, 2]
P [0, 1, 1, 2, 2, 2, 3]
C [0, 0, 0, 0, 0, 0, 0]
A [0, 0, 0, 0, 0, 0, 0]
K [0, 0, 0, 0, 0, 0, 0]
==============
4
      A  C  A  Y  K  P  
  [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 1, 1, 2, 2, 2, 2]
P [0, 1, 1, 2, 2, 2, 3]
C [0, 1, 2, 2, 2, 2, 3]
A [0, 0, 0, 0, 0, 0, 0]
K [0, 0, 0, 0, 0, 0, 0]
==============
5
      A  C  A  Y  K  P  
  [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 1, 1, 2, 2, 2, 2]
P [0, 1, 1, 2, 2, 2, 3]
C [0, 1, 2, 2, 2, 2, 3]
A [0, 1, 2, 3, 3, 3, 3]
K [0, 0, 0, 0, 0, 0, 0]
==============
6
      A  C  A  Y  K  P  
  [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 1, 1, 2, 2, 2, 2]
P [0, 1, 1, 2, 2, 2, 3]
C [0, 1, 2, 2, 2, 2, 3]
A [0, 1, 2, 3, 3, 3, 3]
K [0, 1, 2, 3, 3, 4, 4]

---

코드🐱‍👓

A = input()
B = input()

arr = [ [0 for i in range(len(A)+1)] for j in range(len(B)+1) ]

ans = 0
for i in range(1, len(B)+1):
    al = B[i-1]
    for j in range(1, len(A)+1):
        if al == A[j-1]:
            arr[i][j] = arr[i-1][j-1] + 1
        arr[i][j] = max(arr[i][j], arr[i][j-1], arr[i-1][j])
        ans = max(arr[i][j], ans)
print(ans)

코드 설명

        arr[i][j] = max(arr[i][j], arr[i][j-1], arr[i-1][j])

 

12번째 줄에 코드이다.

10,11 줄에 if문을 통해서 arr[i][j]의 최신화를 시켜주었다. 그러므로 결국 12번째 줄은 문자가 일치하지 않는 경우 arr[i][j]의 값을 업데이트해주기 위해 만들어두었다.

---

(사지방은 캡쳐해도 편집이 안 되네요..)