[Python][백준][5582] 공통 부분 문자열 (DP)

🍋 문제링크

www.acmicpc.net/problem/5582

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 248460 KB

시간 : 564 ms

🍉 Code

answer = 0
str1, str2 = input(), input()

#dp=[[0 for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)]
dp=[[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]

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

print(answer)

🥝 메모

• 이중 for문을 돌다가 같은 문자를 만나게 되면 그전까지의 공통 부분 문자열 길이 + 1을 저장한다

<2차원 배열 초기화하는 방법>

arr = [[0 for _ in range(A)] for _ in range(B)]

arr = [[0] * (A) for _ in range(B)] 

arr = [[0] * A ] * B

😡 마지막 방법은 사용하지 말것!

→ * 을 사용하면, 주소값을 복사하여 2차원 배열을 만드는 것이기 때문에 arr[0][x]을 수정하면 같은 주소를 공유하는 arr[0][x], arr[1][x], arr[2][x] 의 값이 한번에 변경되는 문제가 발생한다.