7977번 - 크리스 마틴 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 308 | 146 | 130 | 55.085% |
문제
미친 과학자 창호는 어젯 밤 구재현을 납치해서, 구재현의 DNA를 추출했다. 인간의 DNA의 길이는 n이며, A, C, G, T 4개의 염색체로 구성되어 있다.
창호는 매일 자신을 놀리던 구재현을 좋아하지 않고, 대신 잘 생긴 콜드플레이의 크리스 마틴을 더 좋아한다. 이러한 경험을 토대로 창호는 이론을 하나 만들었다. 창호의 이론에 따르면, 구재현의 DNA와의 유사도가 최소인 DNA가 크리스 마틴의 DNA이다.
두 DNA의 유사도는, 두 DNA 간의 최장 공통 부분 수열(LCS)의 길이를 뜻한다. 어떠한 DNA의 부분 수열은, 그 DNA에서 0개 이상의 원소를 제거해서 만들 수 있는 또 다른 DNA 수열을 뜻한다. 두 DNA A, B의 최장 공통 부분 수열은, A와 B의 부분 수열이면서, 길이가 최대인 수열들을 뜻한다.
사실 잘 몰랐겠지만, 여러분도 지금 창호에게 납치되어 있다. 크리스 마틴의 DNA를 구하지 못하면 여러분에게 무슨 일이 일어날 지 모른다. 빨리 크리스 마틴의 DNA를 구하자. 가능한 답이 여러 가지일 경우, 아무거나 출력하면 된다.
입력
첫 번째 줄에 인간 DNA의 길이 n이 주어진다. (1 ≤ n ≤ 10, 000) 이 주어진다.
이후 길이 n의 DNA 문자열이 주어진다. 문자열의 모든 문자는 A, C, G, T 넷 중 하나다.
출력
첫 번째 줄에 최소 유사도 c 를 출력한다.
두 번째 줄에 이를 만족하는 길이 n의 문자열을 출력한다. 가능한 답이 여러개 일 경우, 아무거나 출력하면 된다.
예제 입력 1
4 GACT
예제 출력 1
1 TCAG
출처
ICPC > Regionals > Europe > Central European Regional Contest > Poland Collegiate Programming Contest > AMPPZ 2012 D번
High School > 경기과학고등학교 > 나는코더다 2016 송년대회 C번
- 문제를 번역한 사람: koosaga
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호