LCS [백준 9251] - python

 

def BOJ9251() :
  first = input()
  second = input()
  array = [[0] * (len(second) + 1) for _ in range(len(first) + 1)]
  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] + 1
      else :
        array[i][j] = max(array[i-1][j], array[i][j-1])
  
  print(array[len(first)][len(second)])

BOJ9251()

 

접근방법 :

1. 이차원 배열로 접근 

2. 비교하는 문자열이 같다면 대각선에서 길이를 더해주자 

3. 비교하는 문자열이 다르다면 이전까지의 최대값을 알아야 하므로 행 -1, 열-1 값중 최댓값을 가져오자

 

장애물 이었던 것 :

1. 직접 해보는 순간 문제는 다 해결된다. 가끔 해보기도 전에 겁을 지레 먹고 백기를 드는 경우가 있는것 같다

 

 

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

9251번: LCS