[python] SWEA - 3304. 최장 공통 부분 수열

🤔문제 해결

• D3 | DP (LCS)

💨 역시 SWEA의 난이도는 믿을게 못된다. 이게 겨우 D3라니...

💨 [python] 백준 - 9251. LCS (참고)

💨 지난번에 백준에서 한번 풀었고, 코딩테스트할 때 한번 풀었고, 이번에 다시 푸니깐 어느정도 이해가 된거 같다.

💻소스 코드

# 입력
T = int(input())
Ns = [input() for _ in range(T)]

# 풀이 - LCS
results = []
for tc in range(T):
    A, B = Ns[tc].split()
    dp = [[0] * (len(A) + 1) for _ in range(len(B) + 1)]

    for i in range(1, len(dp)):
        for j in range(1, len(dp[i])):
            # 같을 떄
            if B[i - 1] == A[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            # 다를 때
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    results.append((dp[-1][-1]))

# 출력
for tc in range(T):
    print(f'#{tc + 1} {results[tc]}')
 

📕문제 확인

출처: SW Expert Academy

SW Expert Academy