원형 DNA
시간 제한3초메모리 제한512 MB
여러 유전자 유형의 시작과 끝 마커가 원형으로 배열되어 있을 때, 자른 뒤 각 유형의 마커가 올바르게 중첩되는 유형 수가 최대가 되는 절단 위치를 찾는다.
문제
생물정보학 연구실에서 DNA를 연구하는 인턴이 되었다. DNA 한 가닥은 여러 유전자로 이루어져 있고, 유전자들은 유전자 타입이라는 서로 다른 범주로 나뉜다. 유전자 타입은 유전자 마커라는 특정 염기서열로 구분된다. 각 유전자 타입 i는 고유한 시작 마커 si와 고유한 끝 마커 ei를 가진다. 세균 배양, 세포 추출, 단백질 공학 등 여러 힘든 작업을 거친 끝에, 연구실에서는 마커 사이에 있는 유전 물질을 모두 제거하고 유전자 마커만 남긴 형태로 DNA를 변환할 수 있다.
연구실에서는 유전자 해석이 특정 유전자 타입의 마커들이 올바르게 중첩된 구조를 이루는지에 따라 달라진다는 흥미로운 가설을 세웠다. 주어진 마커 열 w에서 유전자 타입 i의 마커들이 올바르게 중첩되는지 판정하려면, w에서 유전자 타입 i의 마커(si와 ei)만 남긴 부분열을 고려해야 한다. 이때 어느 마커도 빠뜨리지 않는다. 다음 구조만이 올바르게 중첩된 구조로 인정된다.
- siei
- siNei (N은 올바르게 중첩된 구조)
- AB (A와 B는 올바르게 중첩된 구조)
컴퓨터를 전공했기 때문에 이 성질을 조사하는 일을 맡게 되었지만, 문제가 하나 더 있다. 연구실에서는 원형 DNA라는 특별한 종류의 DNA를 연구한다. 원형 DNA는 닫힌 고리를 이루는 DNA다. 원형 DNA에서 중첩을 연구하려면 고리를 어느 위치에서 자른 뒤 마커 열을 얻어야 한다. 이때 읽는 방향은 분자적 성질에 따라 고정된다. 따라서 유전자 타입 i가 올바르게 중첩되는지는 원형 DNA를 어디에서 자르는지에도 달려 있다. 올바르게 중첩된 구조를 이루는 유전자 타입의 수를 최대로 만드는 절단 위치를 찾아야 한다. 그림 D.1은 예제 입력 1에 대응하는 예를 보여 준다. 표시된 위치에서 자르면 유전자 타입 1의 마커들이 올바르게 중첩된다.
그림 D.1: 예제 입력 1과 최적의 절단 위치를 나타낸 그림.
입력
첫째 줄에 DNA의 길이 n (1 ≤ n ≤ 106)이 주어진다. 둘째 줄에 DNA 서열, 즉 n개의 마커가 주어진다. 각 마커는 문자 c와 정수 i로 이루어지며, c ∈ {s, e}는 시작 마커인지 끝 마커인지를 나타내고 i (1 ≤ i ≤ 106)는 마커의 유전자 타입이다. 주어진 DNA 서열은 원형 DNA를 임의의 위치에서 잘라 얻은 것이다.
출력
올바르게 중첩된 구조를 이루는 서로 다른 유전자 타입의 수를 최대로 만드는 절단 위치 p와 그 최대 개수 m을 한 줄에 출력한다. DNA는 p번째 입력 마커 바로 앞에서 자른다. 예를 들어 그림 D.1에 나타난 절단 위치는 p = 3이다. m의 최댓값을 내는 절단 위치가 여러 개라면 그중 가장 작은 p를 출력한다.