BOJ 9252

쉬운 문제인 줄 알았으나 생각보다 복잡했던.. 그러나 방법을 찾으면 간단한.. 🤬

Input

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

import sys
input = sys.stdin.readline

str1 = "0" + input().strip()
str2 = "0" + input().strip()

DP

맨 처음 접근 방식은 중첩 for문을 돌면서 글자가 같으면 index를 동시에 증가시키고 이 작업을 반복한 후 최대 값을 출력하는 거였다. 근데 이렇게 하면 동일한 수열이 처음으로 만나는 글자부터가 아니라 중간에 만나는 글자부터 시작할 수 있기 때문에 아예 틀린 방식이 됨.

두번째는 방식은 맞는데 시간 초과가 떴다. 4중 for문을 돌렸기 때문^.< 아주 초과가 날 수 밖에… 그래도 접근 방식은 맞았다. 이 문제를 어떻게 풀어야 할지 제대로 파악하지 않고 접근했기 때문에 1번째 방식처럼 생각했던 거라, 제대로 어떻게 풀어야 할지부터 파악했다. dp를 2차원 배열로 생성해야 한다는 힌트만 얻고 풀어봤는데, 실제로 첫번째에서도 dp는 2차원 배열일 수 밖에 없었어서 조금만 더 생각해보면 이 힌트도 없어도 됐다. 암튼 조건을 더해보면,

• 각 string의 길이를 배열 크기로 설정해서 2차원 배열 dp을 만들고

  dp = [['']*len(str2) for _ in range(len(str1))]

• 2중 for문을 돌면서 동일한 글자일 시 dp[i-1][j-1] 에 저장되어 있는 str에 해당 글자를 더하면 된다.

  for i in range(1, len(str1)):
    for j in range(1, len(str2)):
      if str1[i] == str2[j]:
        dp[i][j] = dp[i-1][j-1] + str1[i]

• 동일한 글자가 아니면 상/좌 dp 중 긴 str을 가져오면 된다.

  else:
    if len(dp[i-1][j]) > len(dp[i][j-1]):
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = dp[i][j-1]

  결국 동일한 글자를 만나고 난 후에는 각 string의 index를 하나씩 증가시켜서 검사를 진행해야 하기 때문에, 꼭지점처럼 해당 index에 그때까지의 수열을 저장하게 된다.

Output

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를,

둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

print(len(dp[len(str1)-1][len(str2)-1]))
print(dp[len(str1)-1][len(str2)-1])