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) 설치횟수의 최솟값을 구한다. 설치할때만 이동거리를 +1해주고, 그렇지 않은 노드간의 연결은 +0 (2) 즉 간선간의 가중치가 다르므로(1 or 0) bfs가 아닌 다익스트라를 이용한다. (bfs로 탐색하면, 처음으로 다른문(#)을 찾은 경우가 거울의 최소설치가 아닌, 거울설치에 제약이 없을 때 최소이동 경로가 된다. 따라서 모든경우를 다 탐색한 후 그 중 최소설치횟수를 찾아야함.) (3) 이 문제는 특히 이동방향 상의 제약(빛은 직진만함)이 있기 때문에 한 노드(r,c)에 총 4번까지 방문이 가능하다. 따라서 한 노드 nodeDist[r][c]에 4방향의 저장소를 만든다 즉 nodeDist[r][c][k] : r,c에 k방향일때의 최소 설치횟수 ​ 2. 소스코드 import heapq ..

1. 풀이 (1) 각 성별을 정렬한다. 남자성격과 여자성격을 정렬했을 때 총 차이의 합이 최소가 되기위해선 항상 아래의 조건이 만족한다. (n번째남자와 매칭된 여자의 성격수치) j이면 j여자에게 잘맞는 여러명의 남자중 하나를 고른다 dp[i][j]=min(dp[i][j],d[i-1][j]) - ij: d[i][j]=min(d[i][j],d[i-1][j]) ..

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