시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 650 | 100 | 53 | 20.307% |
알파벳 소문자로 이루어진 단어 T와 패턴 P가 있다. 이때, T에 문자를 적절히 삭제해서 P가 되는지 확인해보려고 한다.
예를 들어, 단어 programming에서 적절히 문자를 삭제한다면, pong, program, roaming을 얻을 수 있다. 하지만, 순서는 유지되어야 하므로 map은 만들 수 없다.
T는 문자 방정식로 인코딩 되어있다. 이 방정식은 알파벳 대문자로 되어있는 변수를 사용한다.
모든 방정식은 다음과 같은 형태를 갖는다.
또한, 어떤 변수가 왼쪽에 있는 경우는 단 한번만 나오며, A에 대한 방정식을 풀 때, 우변에 다시 A가 나오는 경우가 없다.
따라서, 이 방정식은 항상 유일한 해를 가진다. 예를 들어, 다음과 같은 방정식을 살펴보자.
위의 방정식을 풀면, START = goodtimesbadtimes 가 된다.
패턴 P와 문자 방정식, 그리고 어떤 변수가 T인지 주어졌을 때, T에서 문자를 적절히 삭제하면 P가 되는지 알아보는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.
첫째 줄에 정수 K (1 <= K <= 500) 가 주어진다. 이 값은 방정식의 개수이다. 다음 K개의 줄에는 방정식이 주어진다. 방정식은 위에서 설명한 2가지 형태 중 하나이고, 공백으로 구분되어져 있는 단어, +, =로만 이루어져 있다. 모든 단어와 변수의 이름은 최대 5글자이다. 다음 줄에는 어떤 변수가 T인지 주어진다. 그리고 마지막 줄에는 패턴 P가 주어진다.
P의 길이는 최대 2,000이다.
각 테스트 케이스에 대해서, T의 문자를 적절히 삭제해서 P를 만들 수 있으면 YES를, 아니면 NO를 출력한다.
1 6 START = FIRST + SECND FIRST = D + E SECND = F + E D = good E = times F = bad START debate
YES