백준온라인 2306번 [유전자][C++]

www.acmicpc.net/problem/2306

2306번: 유전자

---

나의 풀이 

최대 길이가 정의되는 경우는 1) KOI유전자 + KOI유전자 또는 2) KOI유전자 안에 KOI유전자 가 들어가 있는 구조이므로

최대길이를 구하려고 할 때는 작은 것부터 결과를 이끌어내는 다이내믹 프로그래밍으로  풀어야 된다고 생각했다.

 

입력으로 주어진 문자열을 S라고 할 경우

i <=j 인 인덱스에 대하여 \(dp [i][j]\)를 정의할 수 있다.

 

\(dp [i][j]\)를 i index부터 j index까지 이루어진 문자열의 최대 KOI유전자 길이라 하면

 

위에서 정의한 두 가지만 판별해주면 된다

 

\(S [i]\)와 \(S [j]\) 같을 경우 경우 1에 해당이 되므로 \(dp [i+1][j-1]+2\) 로 초기화 해준후

 

\(S [i]\)부터  \(S [j]\) 까지 경우 2처럼 쪼개어 봤을 때 더 큰 최대 길이 인지도 고려하여 주면 된다.

 

---

코드