5039: 공통 부분 수열 확장
[만든사람 : CodingPanda-admin 2024/01/15]
문제 설명
어떤 수열에서 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가 확장 가능한지 불가능한지 판별하는 프로그램을 작성하라.
두 개의 수열이 주어졌을 때, 두 수열에 공통으로 나타나는 부분수열을 두 수열의 공통부분수열이라 한 다. 예를 들어, 위 두 수열 X와 Y 가 주어졌을 때, baa 는 X와 Y 의 공통부분수열이지만, aab는 X와 Y 의 공통부분수열이 아니다.
두 수열 X와 Y 의 공통부분수열 W가 주어졌을 때, W가 확장 가능한지 아닌지 판별하려고 한다. W의 한 위치에 어떤 원소를 추가하여 더 긴 공통부분수열을 만들 수 있으면 W는 확장 가능하고, 그렇지 않으면 W 는 확장 불가능하다고 정의한다. 예를 들어, 위의 X와 Y 가 주어졌을 때, 공통부분수열 baa는 baba로 확장 가능하다. 하지만, 공통부분수열 ca는 더 이상 확장할 수 없다.
두 수열 X, Y 와 두 수열의 공통부분수열 W가 주어졌을 때, W가 확장 가능한지 불가능한지 판별하는 프로그램을 작성하라.
입력 설명
첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
다음 3 × T개의 줄에 테스트 케이스의 정보가 주어진다.
각 테스트 케이스는 세 줄로 구성되고, 각 줄에 수열 X, Y , W가 각각 주어진다.
각 수열은 공백 없이 연속된 영어 소문자로 주어진다.
• 하나의 입력 데이터에서 1개 이상 100개 이하의 테스트 케이스를 해결해야 한다.
• |X|의 합과 |Y |의 합은 각각 200 000 이하이다.
• W는 X와 Y 의 공통부분수열이다.
• 수열은 영어 소문자로만 구성된다.
(테스트 케이스 비율)
1. (14%) |W| = 1
2. (17%) |X|의 합과 |Y |의 합은 각각 300 이하이다.
3. (25%) |X|의 합과 |Y |의 합은 각각 20 000 이하이다.
4. (44%) 추가 제약 조건 없음.
다음 3 × T개의 줄에 테스트 케이스의 정보가 주어진다.
각 테스트 케이스는 세 줄로 구성되고, 각 줄에 수열 X, Y , W가 각각 주어진다.
각 수열은 공백 없이 연속된 영어 소문자로 주어진다.
• 하나의 입력 데이터에서 1개 이상 100개 이하의 테스트 케이스를 해결해야 한다.
• |X|의 합과 |Y |의 합은 각각 200 000 이하이다.
• W는 X와 Y 의 공통부분수열이다.
• 수열은 영어 소문자로만 구성된다.
(테스트 케이스 비율)
1. (14%) |W| = 1
2. (17%) |X|의 합과 |Y |의 합은 각각 300 이하이다.
3. (25%) |X|의 합과 |Y |의 합은 각각 20 000 이하이다.
4. (44%) 추가 제약 조건 없음.
출력 설명
출력설명
입력 예시 Copy
2
ababca
cbabba
baa
aaabbbccc
caacbbc
ccc
출력 예시 Copy
1
0