9251

날짜 : 2023. 04. 25

사용 언어 : python

 

문제

 

 

코드

import sys
import itertools
a = sys.stdin.readline().rstrip()
b = sys.stdin.readline().rstrip()
p = len(a)
q = len(b)
dp = [[0] * (q + 1) for _ in range(p + 1)]
for i in range(1, p + 1):
    for j in range(1, q + 1):
        if a[i-1] == b[j-1]:  # 같다면
            dp[i][j] = dp[i-1][j-1] + 1  # 부분수열 추가=
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
"""for i in dp:
    print(i)"""
print(dp[p][q])

 

풀이

- 문자열 a와 b를 입력받은 후 비교용 2차원 리스트 dp를 생성한다.

- 문자열 a를 기준으로 b를 비교하면서 해당 문자(a[i])가 비교대상 문자(b[j])와 동일한 경우 북서쪽 리스트의 값에 1을 가산하여 저장한다.

(위에서 내려온 값을 그대로 가산하는 경우 중복하여 비교하게 되므로 인덱스가 겹치지 않도록 대각선 값을 가져와 가산)

- 만약 서로 다른 경우, 위의 값, 혹은 좌측의 값 중 큰 값을 가져온다.(갱신 없이 가져오는 케이스)

- 이를 반복 후 가장 마지막 인덱스의 값을 출력한다. 

ACAYKP를 기준으로 CAPCAK의 부분수열 길이 비교

 

알게된 점

- 2차원 리스트를 활용한 DP 문제였다.

- 맨 처음 combination을 활용하여 문제를 풀었지만 시간제한 이슈로 인해 TLE가 발생했고, 어떻게 DP를 이용할까 고민한 결과 마땅한 아이디어가 떠오르지 않았다.

- 부분수열을 각각 만들어서 비교해야 하나 고민했는데, 다른 사람의 풀이를 참고해보니 원소 하나를 대상으로 비교하면서 값을 갱신해 나가는 것이 문제의 포인트였다.

 

 

참고 사이트

- https://zidarn87.tistory.com/293

파이썬 / BOJ 백준 / 9251 LCS - dp