[BOJ] 1042번: 움

https://www.acmicpc.net/problem/1042

처음 문제를 본 후로 무려 4개월이 지난 지금에야 해결에 성공했네요. 뭔가 DP스럽게 생겼기 때문에 우선 $D_i$를 DNA[1 to i]에서 만들 수 있고 DNA[1 to i-1]에서는 만들어낼 수 없는 unique DNA sequence의 갯수라고 합시다.(편의상 1-indexed로 둡시다.) 예를 들어

AAAAAAA

1

AAA test

일 경우 D는 (0,0,1,0,0,1,0)입니다.

이 때 $D_i$를 갱신하기 위해서는 $DNA_i$가 끝에 오는 새로운 코돈이 장착되어야 합니다. 이를 위해 A,C,G,T의 등장 위치를 기억하고 있다가 $A A + DNA[i]$, $A C +DNA[i]$, $A G+ DNA[i]$ , ... 등이 만들어지는 위치를 체크합니다. 이 때 i 이전에 동일한 코돈이 언제 등장했는가를 기억하고 있어야 합니다. 이를 이용해 D 테이블을 채워나가야 하고, 세세하게 더 설명해야할 게 많은데 넘어갈게요.. 코드를 참고해주세요.

https://github.com/blisstoner/BOJ/blob/master/1042.cpp