접근 주어진 문자열의 각 문자를 결과 문자열(ans)에 추가한다. 만약 ans[-1] 이 폭발 문자열의 마지막 bomb[-1] 과 같다면 ans[-len(bomb):] 과 bomb[:] 을 비교하여 같으면 폭발시킨다. 사고 worst case time complexity 가 10**6 이길래 O(n) 으로 되는 문제인가 고민했다. 넉넉히 된다. 조건을 이해했을때 ‘모든 폭발 문자열이 폭발하고 새로운 문자열이 생긴다’ 여서 폭발 문자열을 발견할때마다 폭발하는거랑 결과가 혹시 다른가 고민해보았다. 반례가 떠오르지 않아 O(n) 스택으로 풀었다. 한가지 처음에 arr = arr[0:arr - len(bomb)] 이렇게 넣었다가 TLE 떴다. 저렇게 넣어도 파이썬이 optimization 하지 않을까 했는데 정직하게 주어진 인덱스만큼 복사하는것 같다. pop으로 뒤에 있는 문자열을 날리는 방법으로 풀어야 한다. ...
접근 처음 두 줄의 LCS 를 찾고, 그 결과와 마지막 줄의 LCS 를 찾는 순차적인 방법으로도 가능하다. 하지만 3차원 dp 로 처리하는 방법이 확장 가능성이 있기에 더 좋은 접근법이라 생각한다. import sys input = sys.stdin.readline f = input().strip() s = input().strip() t = input().strip() fl = len(f) sl = len(s) tl = len(t) dp = [[[-1] * tl for i in range(sl)] for j in range(fl)] def LCS(a, b, c): if a < 0 or b < 0 or c < 0: return 0 if dp[a][b][c] == -1: dp[a][b][c] = 0 if f[a] == s[b] == t[c]: dp[a][b][c] = LCS(a - 1, b - 1, c - 1) + 1 else: dp[a][b][c] = max(max(LCS(a, b - 1, c), LCS(a - 1, b, c)), LCS(a, b, c - 1)) return dp[a][b][c] print(LCS(fl - 1, sl - 1, tl - 1))