[BOJ] 9251

less than 1 minute read

LCS

9251번 https://www.acmicpc.net/problem/9251

두 문자열 s1, s2가 있을 때,
s1[i] != s2[j] 라면 s1[i]와 s2[j]두가지가 각각 안쓰이는 경우를 고려해 LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]),
s1[i] == s2[j]라면 s1[i]와 s2[j]는 무조건 LCS에 포함되므로 LCS[i][j] = 1 + LCS[i - 1][j - 1]
임을 이용하면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/9251.cpp

Categories:

Updated:

Leave a comment