DNA 단백질 변화 실험 timer 2s memory 256MB

생명공학 박사 진욱이는 몇몇 과학자들을 데리고 외계 생명체의 DNA를 가지고 실험을 하고 있다.

그들은 아주 놀라운 발견을 했는데, 그 내용은 다음과 같다. 그들의 DNA는 4종류의 단백질로 이루어져 있고, 고리 모양이며(즉 시작과 끝이 연결되어 있으며), 매 초마다 정해진 규칙에 의해 변화한다.

과학자들은 편의성을 위해 4종류의 단백질을 A, B, C, D로 칭하기로 했다 (지구인의 단백질이 ATGC인것처럼 말이다).

단백질은 자신의 오른쪽에 있는 단백질의 종류에 따라 다음과 같은 규칙으로 변화한다. 과학자들은 변화 규칙을 가지고 다음과 같은 표를 만들었다. 

가로는 현재 위치에 있는 단백질을 뜻하고, 세로는 현 위치 오른쪽에 있는 단백질을 뜻한다.

표 안의 내용은 1초 뒤 현재 위치에 있던 단백질이 변하는 종류를 뜻한다. 예를 들어, i번째 위치의 단백질이 C이고, i+1번째 단백질이 B이면, i번째 단백질은 1초 후 D가 된다. 또한, i번째 위치의 단백질이 A이고, i+1번째 위치의 단백질이 B이면, i번째 단백질은 1초 후 B로 변화한다. 이 DNA는 고리 모양이기 때문에, 원형 리스트의 형태를 띠고 있고, 이는 다시 말해 맨 끝에 있는 단백질의 오른쪽은 맨 처음에 있는 단백질이다.

문제는 생명체의 종류에 따라 DNA의 길이가 무진장 길 수도 있다는 것이다. 그래서 진욱이는 프로그래밍 천재인 당신에게 입력된 DNA가 K초 후에 어떻게 변할지 알려주는 프로그램을 작성해 달라고 했다.

진욱이를 도와주자.