3998번 - 단백질 식별 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 172 | 52 | 23 | 16.667% |
문제
단백질은 아미노산의 연결체이다. 단백질은 이중 질량 분석기 (MS2)를 이용해서 단백질의 서열을 알아낼 수 있다.
문제를 풀기 위해 다음과 같은 상황을 가정한다.
- 단백질은 최대 400개 아미노산이 연결된 형태이다.
- 아미노산은 두 종류 P와 Q만 있다.
- P의 질량은 97.05276돌턴, Q의 질량은 128.05858돌턴이다.
MS2의 결과는 실수의 집합이며, 각각의 실수는 피크라고 부른다. 집합은 단백질의 모든 prefix와 suffix의 질량이 포함(전체 단백질의 질량 포함)되어 있으며, 다른 숫자는 포함되어 있지 않다.
알 수 없는 단백질을 MS2로 실험한 결과가 주어진다. 실험은 오차가 발생할 수 있기 때문에, 결과는 아래 조건을 만족한다.
- 일부 prefix와 suffix의 결과는 집합에 포함되어 있지 않다.
- 단백질의 prefix/suffix 질량에 해당하지 않는 피크가 집합에 포함되어 있을 수도 있다. 이러한 피크를 노이즈 피크라고 한다.
- 모든 피크는 양수이다.
- 가장 큰 피크는 단백질 전체 질량이다.
- prefix/suffix 질량에 해당하는 피크는 정확한 값이다.
실험 결과가 주어졌을 때, 최대 피크가 단백질의 질량이면서, 노이즈 피크의 수가 최소인 단백질을 만드는 프로그램을 작성하시오.
입력
첫째 줄에 MS2의 실험 결과인 피크의 수 n이 주어진다. (1 ≤ n ≤ 100,000)
다음 n개 줄에는 i번째 피크 pi가 주어진다.
항상 문제의 모든 조건을 만족시키며, 모든 피크는 다르다. 각 피크는 소수점 최대 5째자리까지 주어진다.
출력
길이가 최대 400인 P와 Q로 이루어진 문자열(단백질)을 출력한다. 노이즈 피크의 수를 최소로하는 답이 여러 가지인 경우에는 아무거나 출력한다.
예제 입력 1
6 225.11134 353.16992 353.16991 291.15828 97.05276 128.05858
예제 출력 1
PQQ
힌트
가능한 단백질은 PQQ와 QQP이다. 두 단백질 모두 291.15828, 353.16991 결과를 제외하면 얻을 수 있다.
출처
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2012 I번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호