MCS > 문제은행

본문 바로가기


실전대비 Level2

1155 : MCS

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 66 회    시도횟수: 286 회   



ACGT로만 이루어진 염기서열(DNA sequence)이 존재한다.
염기 서열에서 만들 수 길이가 k인 부분문자열(substring: 문자열 내에서 연속된 부분을 잘라서 만들 수 있는 문자열)들 중에서 사용한 문자의 순서가 다르더라도, 사용한 각 문자들의 빈도가 일치할 경우 두개의 부분문자열을 유사한 것으로 친다고 하자.
이 경우 가장 많이 등장하는 유사한 길이 k의 부분문자열의 빈도수를 구하는 프로그램을 작성하라.

 

예를 들어 염기서열이 "GCAGGAGCGCCAGG"라고 주어졌을 경우 가능한 길이가 3인 부분 문자열은 GCA, CAG, GGA, GAG,…, CAG등이 존재하고, AGG와 GGA, GAG 그리고 AGG가 유사하기 때문에 이 경우 4개의 서로 유사한 부분문자열이 존재한다.


입력의 첫 번째 줄에는 k(1≤k≤1,000)가 입력된다. 그 다음 줄에는 길이 60,000이하의 A와 C, G 그리고 T로 이뤄진 염기서열 문자열이 입력된다.



입력된 염기서열 안에서 가장 많이 등장하는 길이 k의 부분문자열의 등장횟수를 출력한다.


[Copy]
3 
GCAGGAGCGCCAGG
[Copy]
4





ACM-ICPC 2008 Seoul Regional Problem B - MCS

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.