[BOJ] 2306번: 유전자

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


D[i][j]를 DNA[i~j] 내의 가장 긴 유전자 길이라고 정의할 때, D[i][j]는 k = i~j에 대해 D[i][k] + D[k+1][j]의 최댓값입니다.(그리고 만약 DNA[i] = a, DNA[j] = t이거나 DNA[i] = g, DNA[j] = c일 경우, D[i+1][j-1]+2도 고려해주어야 합니다.)


이 점화식이 성립하는 이유는, 만약 DNA[i~j] 내의 최대길이 DNA가 여러 조각으로 잘릴 수 있다면 어떤 k =i~j에 의해 D[i][k]+D[k+1][j]의 합으로 D[i][j]를 나타낼 수 있고, 여러 조각으로 잘리지 않는 형태라면 반드시  DNA[i] = a, DNA[j] = t이거나 DNA[i] = g, DNA[j] = c 이기 때문입니다.


테이블을 채우는 방향은 j-i가 커지는 순서로 채우면 됩니다.


https://github.com/encrypted-def/BOJ/blob/master/2306.cpp

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

[BOJ] 1006번: 습격자 초라기  (0) 2018.01.07
[BOJ] 2261번: 가장 가까운 두 점  (2) 2018.01.07
[BOJ] 2515번: 전시장  (0) 2018.01.07
[BOJ] 2306번: 유전자  (0) 2018.01.07
[BOJ] 2300번: 기지국  (0) 2018.01.07
[BOJ] 2250번: 트리의 높이와 너비  (2) 2018.01.07
[BOJ] 1239번: 차트  (0) 2018.01.07
  Comments
댓글 쓰기