LCS2 [백준 9252] - python

 

def BOJ9252():
  first = input()
  second = input()
  array = [[[0, '']] * (len(second) + 1) for _ in range(len(first) + 1)]
  l = []
  for i in range(1, len(first) + 1):
    for j in range(1, len(second) + 1):
      if first[i-1] == second[j-1]:
        array[i][j] = [array[i-1][j-1][0] + 1, array[i-1][j-1][1] + first[i-1]]
      else:
        if array[i-1][j][0] > array[i][j-1][0] :
          array[i][j] = [array[i-1][j][0], array[i-1][j][1]]
        elif array[i-1][j][0] < array[i][j-1][0]:
          array[i][j] = [array[i][j-1][0], array[i][j-1][1]]
        else :
          array[i][j] = [array[i][j-1][0], array[i][j-1][1]]

  print(array[len(first)][len(second)][0])
  print(array[len(first)][len(second)][1])


BOJ9252()

 

접근방법 : 

1. 길이만 구하는 것이 아니라 제일 긴 문자열도 구해야 했다. dp와 이차원 배열을 이용하였다.

2. 비교 문자열이 같으면 대각선에서 길이와 문자열을 더해준다.

3. 비교 문자열이 다르면 위의 값과 좌측의 값중 길이가 더 긴 값을 선택해준다. 

 

=> 직접 손으로 그려가면서 익히시면 매우 편하실 것입니다

 

 

장애물 이였던 것 :

1. 한번 직접 과정을 그려보니 이해가 되었다.

2. 대각선에서 더하는 것이 잘 떠오르지 않았었다.

 

문제 풀이

 

 

 

 

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

9252번: LCS 2