[백준]9251번 LCS - DP

 

string1 = "0" + input()
string2 = "0" + input()

dp = [[0] * len(string1) for i in range(len(string2))]

for i in range(1, len(string2)):  # 두번째 문자열을 한 개씩 반복하기 위해
    for j in range(1, len(string1)):
        if string2[i] == string1[j]:  # 만약 같은 문자인 경우
            dp[i][j] = dp[i - 1][j - 1] + 1  # BG G -> BGC GC 가 된 경우 "C" 라는 값이 동일하게 들어온 것.
            # 따라서 대각선 왼쪽의 기억되어있는 값 + 1
        else:  # 다른 문자인 경우
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 이전에 비교한 것중 큰 값 선택

print(dp[-1][-1])

 

코드 설명

맨 처음의 리스트는 0으로 이용하기 위해 0을 추가로 저장시켜 string1 과 string2 변수를 할당한다.

그 후 각 문자열의 길이만큼 2차원 리스트 dp 를 초기화 한다.

외부 반복문은 string2, 내부 반복문은 string1 수만큼 이용한다.

만약 같은 문자일 경우에는 두개의 문자열 모두 이전 값에서 + 1을 통해 값을 구해준다. 

다른 문자일 경우에는 이전에 저장된 값중 큰 값을 선택한다.

 

Point : dp를 몇차원으로 설정할 것인지에 대한 고민이 필요한 문제이다. 문자열이 2개이므로 2차원 dp 를 이용한다.

만약 동일한 문자가 새로 들어온 경우라면 + 1 을 해주고 다른 문자가 들어온다면 직전에 저장된 값들중 큰 값을 선택한다.