두 개의 변량을 반영한 값을 만든다면 (#9251)

#9251 LCS https://www.acmicpc.net/problem/9251

 

아.. 그제 풀었던거 오늘 포스팅 하려니까 기억이 가물가물...

 

단순히 dfs로 풀었다.

모든 경우의 수를 탐색하는 것이다. (브루트포스?)

 

그리고 역시나 메모리 초과를 맞이했다.

 

틀린 코드

s1 = input().strip()
s2 = input().strip()

n1 = len(s1)
n2 = len(s2)

visited1 = [False] * n1
visited2 = [False] * n2

N = max(n1, n2)

result1 = {x: [] for x in range(1, n1 + 1)}
result2 = {x: [] for x in range(1, n1 + 1)}


def dfs(depth, s, origin, n):
    if depth >= len(origin):
        return

    if depth < len(origin):
        s += origin[depth]
        if n == 1:
            result1[len(s)].append(s)
        else:  # n==2
            result2[len(s)].append(s)

    dfs(depth + 1, s, origin, n)
    dfs(depth + 1, s[0:-1], origin, n)


dfs(0, "", s1, 1)
dfs(0, "", s2, 2)
# print(result1)
# print(result2)

for i in range(min(n1, n2), 0, -1):
    tmp1 = result1[i]
    tmp2 = result2[i]
    for x in tmp1:
        if x in tmp2:
            print(i)
            exit()

 

 

문제 하단의 알고리즘 분류를 보니 DP라고 나와있었다.

 

하하.. 이걸 어떻게... 하고 찾아보니

2차원 DP였다.

요즘 자꾸 2차원 DP 문제를 마주하게 된다.

나의 한계를 돌파하기 위해서는 꼭 숙달해야 할 부분이었다.

 

다음과 같은 사고방식을 통해 점화식을 찾을 수 있다.

DP에서 점화식을 찾을 때, 수학적 점화식처럼 깔끔한 식이 나올 것이라 기대하지 말자.

또한, 테스트케이스를 손으로 최대한 굴려서, 규칙을 찾아내자.

이게 정말 정말 중요한 과정이다.

 

정답 코드

s1 = input().strip()
s2 = input().strip()

n1, n2 = len(s1), len(s2)
dp = [[0 for _ in range(n1 + 1)] for __ in range(n2 + 1)]

for y in range(1, n2 + 1):  # s1
    for x in range(1, n1 + 1):  # s2
        if s1[x - 1] == s2[y - 1]:
            dp[y][x] = dp[y - 1][x - 1] + 1
        else:
            dp[y][x] = max(dp[y - 1][x], dp[y][x - 1])

print(dp[n2][n1])