BaaaaaaaarkingDog
코딩, 해킹
[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1044번: 팀 선발  (2) 2018.09.16
[BOJ] 16120번: PPAP  (0) 2018.09.15
[BOJ] 16139번: 인간-컴퓨터 상호작용  (0) 2018.09.15
[BOJ] 1042번: 움  (0) 2018.09.15
[BOJ] 3648번: Idol  (0) 2018.09.06
[BOJ] 12982번: 공 포장하기 2  (0) 2018.09.06
[BOJ] 3090번: ŽIVICA  (0) 2018.09.05
  Comments
댓글 쓰기