시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 512 MB (추가 메모리 없음)143362535.714%

문제

대학원생 시철이는 대학원에서도 복전을 한다. 이번엔 무려 생명공학이다!

과제에 짓눌리는 걸 좋아하는 시철이답게, 오늘도 어김없이 세포 배양 과제를 하고 있다.

시철이가 배양하는 세포는 상당히 특이한 성질을 가지고 있다.

  1. 모든 세포는 분열할 때, 좌우로 갈라진다. 세포 분열이 끝나고 나면, 같은 종류의 세포가 하나 더 만들어지는 것이다.
  2. 때때로 세포 분열 중 돌연변이가 발생해, 다른 종류의 세포가 하나 만들어질 수 있다. 돌연변이가 일어나면, 이전과 같은 세포 $1$개와 이전과 다른 세포 $1$개가 만들어지고 이 둘의 순서는 무작위로 정해진다.
  3. 세포 종류에 따라서 돌연변이가 아예 발생하지 않을 수도 있다. 만약 발생한다면, 오직 다른 한 종류로만 가능하다.
  4. 분열하는 세포는 무작위로 정해지고, 동시에 여러 세포가 분열할 수 있다.

불타는 금요일, 시철이는 배양지에 세포 하나를 올려두었다. 다음 주 월요일에 시철이가 연구실로 돌아왔을 땐 모든 세포 분열이 멈춰있는 상태였다. 곧바로 시철이는 이 배양지에 있는 세포들을 관찰했지만, 돌연변이가 너무 많이 생기는 바람에 이 배양지가 본인의 배양지인지 동기의 배양지인지 헷갈리기 시작했다.

과연 배양지에 있는 세포들은 시철이가 올려둔 초기 세포에서 분열이 된 것일까?

입력

첫 번째 줄에 세포 종류의 개수 $N$가 주어진다. ($1 \leq N \leq 26$)

두 번째 줄에 돌연변이를 나타내는 알파벳 소문자 $a_1, a_2, \cdots, a_N$가 공백 단위로 주어진다. 이것은 $i$번째 알파벳에 해당하는 세포의 분열 중 돌연변이가 발생해 $a_i$번째 알파벳에 해당하는 세포가 생길 수 있음을 뜻한다. $a_i$가 $i$번째 알파벳일 경우, 해당 종류의 세포는 돌연변이가 발생하지 않는 것을 의미한다. $a_i$는 $a$부터 $N$번째 알파벳 중 하나다.

세 번째 줄에 초기 세포의 종류를 나타내는 알파벳 소문자 $K$가 주어진다. $K$는 $a$부터 $N$번째 알파벳 중 하나다.

네 번째 줄에 시철이가 관찰한 세포 배열을 나타내는 $S$가 주어진다. $S$의 모든 원소는 $a$부터 $N$번째 알파벳 소문자 중 하나고, 공백 없이 한 줄에 주어진다. ($1 \leq |S| \leq 500$)

출력

관찰한 세포 배열이 초기 세포로부터 생겨날 수 있다면 YES를 출력한다.

그렇지 않으면 NO를 출력한다.

예제 입력 1

5
b c c a b
e
ecbbc

예제 출력 1

YES

세포가 다음과 같이 분열을 하면 충분히 나타날 수 있는 결과이다.

e → eb(돌연변이) → ecb(돌연변이) → ecbb(정상분열) → ecbbc(돌연변이)

예제 입력 2

3
a b c
a
c

예제 출력 2

NO

모든 세포가 돌연변이를 일으키지 않기 때문에 불가능한 배열이다.

출처

University > 연세대학교 > 2021 연세대학교 프로그래밍 경진대회 J번