(백준) 15482 – 한국어 LCS (Python)

by

쉬운 목차

문제

#15482: 한국 LCS (acmicpc.net)

#15482: 한국 LCS

'추천 관련글,

첫 번째와 두 번째 줄에 두 개의 문자열이 지정됩니다. 문자열은 최대 1000자이며 유니코드 U+AC00(a) ~ U+D7A3(HI)로 구성되며 UTF-8로 인코딩됩니다.

www.acmicpc.net

설명

입력 문자열 2개만큼 2차원 배열을 만들어서 해결했습니다.

0 ㅏ 씨 ㅏ 와이 케이 피
0 0 0 0 0 0 0 0
씨 0 0 하나 하나 하나 하나 하나
ㅏ 0 하나 하나 2 2 2 2
피 0 하나 하나 2 2 2 삼
씨 0 하나 2 2 2 삼 삼
ㅏ 0 하나 2 삼 삼 삼 삼
케이 0 하나 삼 삼 삼 삼 4

ACAYK피그리고 cㅏ피CAK LCS는 ACAK이며 어레이의 작동 원리는 위와 같습니다.

그 외에도 Python은 데이터 유형에 대해 실제로 생각하지 않으므로 동일한 코드로 이 문제를 해결할 수 있습니다. 9251: LCS (acmicpc.net)

from sys import stdin
input = lambda : stdin.readline().strip()

A = " " + input()
B = " " + input()
dp = ((0) * (len(A)) for _ in range(len(B)))

for i in range(1, len(B)) :
      for j in range(1, len(A)) :
            if A(j) == B(i) :
                  dp(i)(j) = 1 + dp(i - 1)(j - 1)
            else :
                  dp(i)(j) = max(dp(i - 1)(j), dp(i)(j - 1))
print(dp(-1)(-1))