[백준(BOJ)] 9252번 : LCS 2 - PYTHON[파이썬]

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

---

 

⊙ 문제 접근 과정

 

2차원 배열을 사용하여 문제를 풀었다.

각 문자의 길이만큼 배열을 만들어주고, 규칙성을 찾아내어 정보를 담아준다.

 

i for문과 j for문을 사용해 두 문자열을 비교해주는데 일치하면 dp [i][j] = dp [i - 1][j - 1] + 문자 저장해준다.

일치하지 않으면 d[i-1][j] 와 dp [i][j-1]에서 길이가 긴 것을 dp [i][j]에 넣어준다.

 

---

 

⊙ 문제 풀이

 

import sys
input = sys.stdin.readline

a = list(input().rstrip())
b = list(input().rstrip())
dp = [[""] * (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] + a[i-1]
        else:
            if len(dp[i-1][j]) >= len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]

if len(dp[-1][-1]) == 0:
    print(0)
else:
    print(len(dp[-1][-1]))
    print(dp[-1][-1])

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

DP 너무 싫어어

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!