시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 599 | 63 | 40 | 9.479% |
DNA 수열은 A, C, G, T로 이루어져 있다. DNA 수열의 GC-비율은 C와 G의 개수를 수열의 길이로 나눈 값이다. GC-비율이 높은 구간은 유전자의 시작 구간이 될 확률이 높다. 따라서, GC-비율은 매우 중요하다.
매우 긴 DNA 수열에서 수열의 모든 부분 수열 중에서 GC-비율이 가장 큰 부분 수열을 찾는 연구가 활발히 진행중이다. GC-비율이 높은 짧은 부분 수열은 의미없는 경우가 많기 때문에, 길이의 하한(lower bound)을 정해두고 부분 수열을 찾는다.
DNA 수열에서 모든 A와 T를 0으로, C와 G를 1로 바꿔서 길이가 같은 이진수열을 만들 수 있다. 이렇게 만든 이진수열의 평균값은 DNA 수열의 GC-비율과 같아진다.
인덱스 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
수열 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
이진수열이 위와 같이 주어을 때, 길이의 하한이 7이라면 평균이 최대인 부분 수열은 [7,14]가 되고, 평균은 6/8이다. 하한이 5인 경우, 평균이 최대인 부분 수열은 [7,11]이 되고, 평균은 4/5가 된다.
이진수열과 길이의 하한 L이 주어졌을 때, 길이가 적어도 L인 모든 부분 수열 중에서 평균이 최대인 부분 수열을 찾는 프로그램을 작성하시오. 같은 평균을 가지는 부분 수열이 여러 개인 경우, 길이가 짧은 것을 찾으면 된다. 길이가 짧은 것이 여러 개인 경우에는, 시작 위치가 앞서는 것을 찾는다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 이진수열의 길이 n(1 ≤ n ≤ 100,000)과 길이의 하한 L(1 ≤ L ≤ 1,000)이 주어진다. 다음 줄에는 길이가 n인 이진수열이 주어진다.
각 테스트 케이스 마다 부분 수열의 시작 위치와 끝 위치를 출력한다.
2 17 5 00101011011011010 20 4 11100111100111110000
7 11 6 9
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2009 D번