[BOJ 2306] 유전자

https://www.acmicpc.net/problem/2306 - 문제 요약 DNA 서열은 4개의 문자 {a,c,g,t}로 이루어진 문자열이다.또한 KOI 유전자는 아래의 3가지 조건을 만족한다.at와 gc는 가장 짧은 길이의 KOI 유전자이다.어떤 X가 KOI 유전자라면 aXt와 gXc도 KOI 유전자이다.어떤 X와 Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다.주어진 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI 유전자를 찾아 그 길이를 출력하시오.  - 알고리즘 정리 DP[a][b] : (s[a], s[b]) 구간에서 KOI 유전자의 최대 길이 우선 위와 같이 DP 테이블 정의를 해 줍니다. 문제에서 제시한 조건을 보면(1) KOI 유전자가 쭉 이어져 있는 경우..

2025.03.27