[백준] 2306: 유전자 - 파이썬

문제 보기

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

2306번: 유전자

 

 

 

---

 

풀이 및 코드

 

해당 문제는 dp를 이용해 푸는 문제이다. 문제의 대략적인 흐름은 LCS문제랑 비슷하다. 만일 LCS 문제를 풀어보지 못했거나 기억이 나지 않는 다면, 공부하고 풀어보는 것을 추천한다!

 

 

필자는 dp에 sequence[i:j]에서의 KOI의 최장 길이를 저장했다. 즉 "acattgagtc"의 예제에서 dp[0][5] 는 "acatt"의 KOI 최장 길이로 4이다. 

 

 

핵심 인사이트는 다음 코드이다. i부터 j까지 k를 돌면서 dp[i][k] + dp[k][j] 가 최대일 때를 찾도록 하였다.

for k in range(i+1, j):
    dp[i][j] = max(dp[i][j], dfs(i, k) + dfs(k,j))

 

 

 

 

 

 

---

삽질 내용

필자는 맨 처음에 dp로 접근하지 않았고 괄호문제처럼 풀었다. for문을 돌면서 다음 알파벳에 따라 경우를 나누었다. a,t인 경우에는 str에 추가해주고 g,c인 경우에는 str에서 짝을 찾아 삭제하거나 다음 문자열로 넘기는 방식으로 코드를 구현하였다. 

 

답이야 올바르게 나오지만 시간 초과였다! 시간 복잡도를 생각해보니, dp에 저장하지도 않고 너무 많이 dfs를 돌렸다. 시간 복잡도 n!로 예상된다..ㅎ 시간초과 나는 게 당연한 코드였다