공통 부분 수열 확장
플래티넘 IV의견: 0
어떤 수열에서 0개 이상의 원소를 삭제해서 얻을 수 있는 수열을 그 수열의 부분수열이라 한다. 예를 들어, aab는 \(X\) = ababca의 부분수열이지만, \(Y\) = cbabba의 부분수열은 아니다.
두 개의 수열이 주어졌을 때, 두 수열에 공통으로 나타나는 부분수열을 두 수열의 공통부분수열이라 한다. 예를 들어, 위 두 수열 \(X\)와 \(Y\)가 주어졌을 때, baa는 \(X\)와 \(Y\)의 공통부분수열이지만, aab는 \(X\)와 \(Y\)의 공통부분수열이 아니다.
두 수열 \(X\)와 \(Y\)의 공통부분수열 \(W\)가 주어졌을 때, \(W\)가 확장 가능한지 아닌지 판별하려고 한다. \(W\)의 한 위치에 어떤 원소를 추가하여 더 긴 공통부분수열을 만들 수 있으면 \(W\)는 확장 가능하고, 그렇지 않으면 \(W\)는 확장 불가능하다고 정의한다. 예를 들어, 위의 \(X\)와 \(Y\)가 주어졌을 때, 공통부분수열 baa는 baba로 확장가능하다. 하지만, 공통부분수열 ca는 더 이상 확장할 수 없다.
두 수열 \(X\), \(Y\) 와 두 수열의 공통부분수열 \(W\)가 주어졌을 때, \(W\)가 확장 가능한지 불가능한지 판별하는 프로그램을 작성하라.
- 하나의 입력 데이터에서 \(1\)개 이상 \(100\)개 이하의 테스트 케이스를 해결해야 한다.
- \(|X|\) 의 합과 \(|Y|\) 의 합은 각각 \(200\,000\) 이하이다.
- \(W\)는 \(X\)와 \(Y\)의 공통부분수열이다.
- 수열은 영어 소문자로만 구성된다.
첫 번째 줄에 테스트 케이스의 개수 \(T\)가 주어진다.
다음 \(3 \times T\)개의 줄에 테스트 케이스의 정보가 주어진다.
각 테스트 케이스는 세 줄로 구성되고, 각 줄에 수열 \(X\), \(Y\), \(W\)가 각각 주어진다.
각 수열은 공백 없이 연속된 알파벳 소문자로 주어진다.
각 테스트 케이스에 대해 확장 가능 여부를 한 줄에 하나씩 출력한다.
확장 가능하면 1, 불가능하면 0을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 14점 | \(|W| = 1\) |
2 | 17점 | \(|X|\) 의 합과 \(|Y|\) 의 합은 각각 \(300\) 이하이다. |
3 | 25점 | \(|X|\) 의 합과 \(|Y|\) 의 합은 각각 \(20\,000\) 이하이다. |
4 | 44점 | 추가 제약 조건 없음. |
2
ababca
cbabba
baa
aaabbbccc
caacbbc
ccc
1
0
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2021 > 1차 대회 > 고등부 3번
평가 및 의견
공통 부분 수열 확장
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
공통 부분 수열 확장