KOI 1차 2021 고3- 공통 부분 수열 확장 > 문제은행 : 정보올림피아드&알고리즘




4730 : 공통 부분 수열 확장

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
20 회   
시도횟수
44 회   

문제

어떤 수열에서 0개 이상의 원소를 삭제해서 얻을 수 있는 수열을 그 수열의 부분수열이라 한다.

예를 들어, aab는 X = ababca의 부분수열이지만, Y = cbabba의 부분수열은 아니다.

 

두 개의 수열이 주어졌을 때, 두 수열에 공통으로 나타나는 부분수열을 두 수열의 공통부분수열이라 한다.

예를 들어, 위 두 수열 X와 Y가 주어졌을 때, baa는 X와 Y의 공통부분수열이지만,

aab는 X와 Y의 공통부분수열이 아니다.

 

두 수열 X와 Y의 공통부분수열 W가 주어졌을 때, W가 확장 가능하지 아닌지 판별하려고 한다.

W의 한 위치에 어떤 원소를 추가하여 더 긴 공통부분 수열을 만들 수 있으면 W는 확장 가능하고, 

그렇지 않으면 W는 확장 불가능하다고 정의한다.

예를 들어, 위의 X와 Y가 주어졌을 때, 공통부분수열 baababa로 확장 가능하다.

하지만, 공통부분수열 ca는 더 이상 확장할 수 없다.

 

두 수열 X, Y와 두 수열의 공통부분수열 W가 주어졌을 때, 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점) 추가 제약 조건 없음. ​

 

 

 

 


입력형식

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.

다음 3 × T개의 줄에 테스트 케이스의 정보가 주어진다.

각 테스트 케이스는 세 줄로 구성되고, 각 줄에 수열, X, Y, W가 각각 주어진다.

각 수열은 공백 없이 연속된 영어 소문자로 주어진다.


출력형식

각 테스트 케이스에 대해 확장 가능 여부를 한 줄에 하나씩 출력한다.

확장 가능하면 1, 불가능하면 0을 출력한다.


입력 예

2
ababca
cbabba
baa
aaabbbccc
caacbbc
ccc

출력 예

1
0

데이타 만든사람 : ohjtgood

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP