2151 거울 설치
14444 가장 긴 팰린드롬 부분 문자열
1053 팰린드롬 공장
14444
팰린드롬 = 기존 문자열과 뒤집은 문자열에서 공통으로 존재하는 부분문자열. 기존 문자열+'#'+뒤집은 문자열 -> suffix array를 구한 후 LCP계산
#은 예외상황을 처리하기 위해 넣는것. LCP를 처리할 때 #을 기준으로 좌우의 suffix array를 비교해야 한다.
1053
1,2,3번은 횟수제한이 없다. 4번은 최대 한번. 이런경우 4번같은 연산을 미리 처리하고 나머지를 처리한다. nC2개를 처리해야 하는데 n의 최대값이 겨우 50이라 부담없이 모두 처리. 1.삽입==2.삭제. 둘다 처리횟수+1이고 똑같은 연산이다. 3번 교환의 경우 교환의 이유가 s[i]==s[j]로 만들기 위함이므로 연산시 d[i][j] = d[i+1][j-1]+1이 된다.
2151
bfs긴 한데 방향이 직선이다. !를 만날경우 cost가 0또는 1로 나뉘므로 deque을 사용했고 기존 방향을 기억하기 위해 방향을 deque으로 선언했다. 기존의 가중치가 0또는 1인 bfs는 x,y를 deque에서 pop한 후 거기에 dx,dy를 이용하여 가기전에 미리 검사하는 방식을 사용했다. 하지만 이번의 경우 !가 있을 때 거울을 설치 또는 설치하지 않는 경우가 생긴다. !가 하나라면 미리 처리할 수 있겠지만 !가 연속해서 계속 나올경우 모두 처러하기 위해서는 재귀적 구조가 필요하고 depth가 난장판이 된다. 그러므로 이 문제는 가기전에 검사하는게 아니라 일단 해당 칸으로 간 후 그곳에 무엇이 있냐에 따라 다음 칸의 cost를 갱신하는 방식을 사용했다. cost별로 pop되므로 가장 먼저 도착한 것이 최소 cost가 된다.