[문제 풀이] 백준 9251

해결 과정

DP 문제 하나 더 풀어보려고 본 문제. 문제는 이해가 갔으나 이걸 어떻게 DP 테이블로 풀지 감이 안와서 다른 링크를 참고했다. 먼저 그림을 그려 이해한 뒤, 코드는 보지 않고 스스로 풀어봤다. 처음에 행과 열을 바꿔서 초기화해서 런타임 에러가 났는데, 이 부분 조심.

 

dp 테이블에 첫 행과 첫 열을 하나씩 더 두고, 0으로 초기화 해둔다. 

이중 for문을 돌면서, 

현재 위치의 a와 b가

같으면, dp[i-1][j-1]의 값에 + 1을 해서 넣고

다르면, dp[i-1][j] 와 dp[i][j-1] 중 더 큰 값을 넣는다.

 

나의 풀이

def solution(a, b):
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[len(a)][len(b)]

a = input()
b = input()
print(solution(a, b))

 

다른 풀이

이 분 블로그 글이 정말 잘 나와있다.