반응형
문제
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
풀이
이차원배열을 사용해 LCS의 길이를 구한 후, 오른쪽 구석에서 부터 탐색하여 문자열을 구할 수 있습니다.
소스코드
후기
LCS의 길이를 구하는 문제는 이미 풀어봤지만, 문자열을 어떻게 구할 수 있을지
2차원 배열을 확인하면서 풀이를 유추할 수 있었습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 9019 DSLR (Swift) (0) | 2023.05.15 |
|---|---|
| [BOJ] 백준 13913 숨바꼭질 4 (Swift) (0) | 2023.05.10 |
| [BOJ] 백준 14003 가장 긴 증가하는 부분 수열 5 (Swift) (0) | 2023.05.04 |
| [BOJ] 백준 14002 가장 긴 증가하는 부분 수열 4 (Swift) (0) | 2023.05.04 |
| [BOJ] 백준 12852 1로 만들기 2 (Swift) (0) | 2023.05.03 |
