5722번 - DNA 부분 수열 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 28 | 6 | 5 | 41.667% |
문제
상근이는 DNA 수열을 연구하는 컴퓨터 과학자이다. 오늘은 두 문자열의 최대 공통 부분 수열을 구해보려고 한다.
알파벳 Σ으로 이루어진 단어 w = a1a2...ar (ai ∈ Σ for i = 1,2,...r)이 있다. w의 부분 수열은 1 ≤ i1 < i2 < .... < is ≤ r을 만족하는 x=ai1ai2...ais 이다. 모든 j = 1,2,...,s-1에 대해서 ij+1 = ij + 1을 만족하는 부분 수열 x를 w의 세그먼트라고 한다. 예를 들어, lovely는 ove의 세그먼트이다. 하지만, loly는 lovely의 부분 수열이지만, 세그먼트는 아니다.
두 단어 w1과 w2의 부분 수열이 되는 단어를 공통 부분 수열이라고 한다. 최대 공통 부분 수열은 w1와 w2의 공통 수열 중에서 길이가 가장 긴 것을 말한다. 예를 들어, w1 = lovxxelyxxxxx, w2 = xxxxxxxlovely인 경우에 w3 = lovely와 w4 = xxxxxxx는 w1와 w2의 공통 부분 수열이다. w4는 길이가 7이며, 두 단어 w1과 w2의 최대 공통 부분 수열이 된다. 길이가 0인 빈 단어는 항상 공통 부분 수열이다.
상근이는 부분 수열이 반드시 길이가 K이상인 공통 세그먼트를 포함해야 한다는 조건을 추가했다. 예를 들어, K=3인 경우에 lovxxelyxxxxx와 xxxxxxxlovely의 공통 부분 수열로 lovely는 가능하지만, xxxxxxx는 가능하지 않다. xxxxxxx에는 길이가 3 이상인 공통 세그먼트가 포함되어 있지 않기 때문이다.
두 단어가 주어졌을 때, 길이가 K 이상인 공통 세그먼트를 포함하는 최대 공통 부분 수열의 길이를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 K가 주어진다. (1 ≤ K ≤ 100) 다음 두 줄에는 알파벳 소문자로만 이루어진 두 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같으며, 103을 넘지 않는다.
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스마다 길이가 K 이상인 공통 세그먼트를 포함한 최대 공통 부분 수열의 길이를 출력한다. 만약, 0보다 큰 공통 수열이 없는 경우에는 0을 출력한다.
예제 입력 1
3 lovxxelyxxxxx xxxxxxxlovely 1 lovxxelyxxxxx xxxxxxxlovely 3 lovxxxelxyxxxx xxxlovelyxxxxxxx 4 lovxxxelyxxx xxxxxxlovely 0
예제 출력 1
6 7 10 0
출처
ICPC > Regionals > Latin America > South America Regional Contests 2008 D번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호