1. 풀이 dp[i][j] : i에서 j문자열까지 만들 수 있는 길이 중 최대 dp[i][j]를 구하기 위해선 아래 두가지를 고려해주면 된다. ​ (1) (A[i]==a and A[j]==t) or (A[i]==g and A[j]==c) 인경우 dp[i+1][j-1]+2 => 양끝이 조건에 만족하면 KOI유전자 ​ (2) dp[i][j]=max(dp[i][j-s]+dp[i+j+1-s][j] (k: 1~j-i)) => () + ()가 가능(각조합에서 최댓값 찾기) 2. 소스코드 A=input() size=len(A) dp=[[0 for j in range(size)] for i in range(size)] for j in range(1,size): for k in range(size-j): dp[k][j ..

1. 풀이 원래 맞았던 문제가 재채점 된 이후 시간초과가 났다. (소스코드1) dfs로 탐색하며 파라미터로 위치와 현재까지의 word를 저장했다. 이후 새롭게 탐색하는 격자의 알파벳이 word에 있는 알파뱃이면 그자리에서 탐색을 종료했다. 풀이는 똑같지만 시간초과를 줄이기 위해 두가지를 바꿔주었다. (소스코드2) (1) 격자의 알파벳이 word에 있는지 확인해 주기 위해 (alpabet in word)를 사용했다. 하지만 이러면 word를 한바퀴 다돌아야 하기 때문에 시간이 오래걸린다. 알파벳은 총 26개이므로, 알파벳의 아스키코드를 인덱스로 하는 길이 26의 visited 리스트를 관리하여 특정 알파벳이 현재까지의 단어에 포함되어있는지를 즉시 알 수있도록 해주었다. ※ 이런류의 탐색에서 시간초과를 많이..