34161번 - OO0OO 점수

문제

제 이름은 똑바로 읽어도 거꾸로 읽어도 우영우입니다. 기러기, 토마토, 스위스, 인도인, 별똥별, 우영우. ...역삼역?

- 드라마 “이상한 변호사 우영우” 中 우영우

현제는 요즘 드라마 “이상한 변호사 우영우”에 푹 빠져있다. 우영우는 똑바로 읽어도 거꾸로 읽어도 우영우다. 심지어 영어로 해도 OO-0-OO여서 거꾸로 읽어도 똑같다.

이렇게 거꾸로 읽어도 똑같은 문자열을 팰린드롬이라고 한다.

팰린드롬 문자열인지 확인하는 방법들 중 하나는 문자열을 뒤집은 뒤 원래 문자열과 같은지 비교하는 방식이 있다.

팰린드롬은 코딩에서 상당히 많이 등장한다. 대표적으로 팰린드롬과 관련된 알고리즘은 매내처 알고리즘이 있으며, 이를 활용하여 선형 시간 내에 모든 중심에서의 최장 팰린드롬의 길이를 구할 수 있다.

KMP나 Z 알고리즘 등을 이용해 최단 팰린드롬을 만들 수도 있으며, 자료구조 이름부터 팰린드롬인 EERTREE를 활용하여 온라인으로 팰린드롬과 관련한 여러 쿼리를 처리할 수도 있다.

팰린드롬은 코딩 및 알고리즘 이외에도 다양한 분야에 활용된다. 1722년 프란츠 요제프 하이든이 지은 교향곡 47번은 팰린드롬이라는 이름도 가지고 있는데, 미뉴에트 악장의 경우 악보가 팰린드롬으로 만들어졌기 때문이다.

프란츠 요제프 하이든이 지은 교향곡 47번 <팰린드롬> 中 팰린드롬 부분

이외에도 다양한 회문 악보가 존재하며, 여러 음악적인 영감을 주었다.

팰린드롬은 특히 생물학에서도 중요하게 등장한다. 우리의 몸에 있는 DNA에서도 팰린드롬을 발견할 수 있다.

DNA는 뉴클레오티드의 이중나선 구조로 이루어져 있으며, 뉴클레오티드는 당, 염기, 인산기로 이루어져 있다. DNA의 당은 디옥시리보오스(Deoxyribose)이며, 염기는 구아닌(Guanine), 아데닌(Adenine), 티민(Thymine), 시토신(Cytosine)의 종류가 있다. 새의 배설물이 굳어서 만들어진 암석 ‘구아노’에서 구아닌이 발견되었고, 이후 새로 발견된 염기와 함께 A(아데닌), T(티민), C(시토신), G(구아닌)으로 표기한다.

염기는 서로 상보적인 결합을 하며 아데닌과 티민은 이중 수소 결합, 구아닌과 시토신은 삼중 수소 결합을 형성한다. 염기들을 DNA를 구성하는 순서대로 AATTCATG와 같이 적어 염기 서열로 표기하며, 대응되는 상보 서열도 정의하여 위의 서열의 상보 서열은 TTAAGTAC이다.

여기서 유전자 가위라는 개념이 나온다. 크리스퍼(CRISPR, Clustered Regularly Interspaced Short Palindromic Repeats)는 주기적으로 반복되는 짧은 회문 염기 서열을 의미하며, 앞 뒤 어느 방향으로 읽어도 똑같다. 예를 들어 염기 서열 GAATTC의 상보 서열은 CTTAAG인데, 상보 서열을 거꾸로 읽으면 원래 서열인 GAATTC가 된다.

DNA는 양쪽 나선의 읽는 방향이 반대이므로, 이 GAATTC 염기 서열의 경우 어떤 나선을 기준으로 읽더라도 같은 결과인 GAATTC를 읽게 된다.

특정 염기 서열을 읽어 제거하는 제한 효소 역시 이런 회문 구조를 읽어 DNA를 절단하며, 이 중 EcoRI가 위의 서열인 GAATTC를 인식하여 제거한다.

유전자 가위는 이런 제한 효소의 성질을 이용하여 손상된 DNA를 절단해 제거하는 기술이다.

유전자 가위는 세대를 거치며 발전해 왔다. 1세대에는 ZFN, 2세대는 TALEN, 3세대의 경우 CRISPR/Cas9으로 발전해 왔다.

특히 3세대 CRISPR/Cas9을 개발한 사르팡티에와 다우드나는 2020년 노벨화학상을 수상할 정도로 혁신적이고 고무적인 기술이다.

회문과 관련된 이야기는 여기까지 하도록 하고, 드라마 “이상한 변호사 우영우”에서 우영우는 아래와 같은 고래 문제를 낸다.

“몸무게가 22ドル$톤인 암컷 향고래가 500ドル$kg에 달하는 대왕오징어를 먹고 6ドル$시간 뒤 1ドル.3$톤짜리 알을 낳았다면 이 암컷 향고래의 몸무게는 얼마일까요?”

정답은 ’고래는 알을 낳을 수 없다’입니다. 고래는 포유류라 알이 아닌 새끼를 낳으니까요. 무게에만 초점을 맞추면 문제를 풀 수 없습니다. 핵심을 봐야 돼요.

현제는 여기에 감동을 받아 다음과 같은 문제를 냈다.

“몸무게가 $A$톤인 암컷 향고래가 $B$kg에 달하는 대왕오징어를 먹고 $C$시간 뒤 $D$톤짜리 알을 낳았다면 이 암컷 향고래의 몸무게는 얼마일까요?”

1ドル\le A,B,C,D\le 10$을 만족하는 모든 10ドル,円 000$개의 정수 튜플 $\left( A,B,C,D \right)$에 대해 문제를 풀어보자.

입력

첫 번째 줄에 문자열 Welcome이 주어진다.

두 번째 줄에 문자열 To The이 주어진다.

세 번째 줄에 문자열 MatKor Cup!이 주어진다.

출력

총 10ドル,円 000$ 줄을 출력한다. 조건을 만족하는 모든 10ドル,円 000$개의 정수 튜플 $\left( A,B,C,D \right)$ 쌍에 대해 문제에 대한 답을 kg 단위로 한 줄에 한 개씩 출력한다. 정답이 없거나 정수가 아니라면 대신 -1을 출력한다. 이때, $\left( A,B,C,D \right)$가 오름차순인 순서로 각 튜플의 답을 출력한다.

주어진 조건 내에서 정답이 998ドル,円 244,円 353$ 미만의 정수 혹은 정답이 없거나 정수가 아님이 보장된다.

제한

10ドル,円 000$개 중 정답이 맞은 개수 당 0ドル.01$점을 부여한다.

단, 출력이 10ドル,円 000$개의 정수가 아닌 경우나 $-1$ 이상 998ドル,円 244,円 353$ 미만의 범위를 벗어나는 경우 틀렸습니다를 받을 수 있으므로, 답을 구하지 못한 경우도 정수를 출력하자.

노트

이 문제의 시간 제한이 0ドル.124$초인 이유는 동우의 생일이 1ドル$월 24ドル$일이기 때문이다.