https://www.acmicpc.net/problem/6240
지금 겨우 풀었는데, 시간초과 났음. 아예 접근이 잘못된건지 아니면 최적화가 잘못 된건지 코너 케이스가 있는건지 모르겠음
내 풀이는 우선 id를 받고 리버스 시켜서 LCS 구해서 공통부분이 아닌 문자에 대해
1. dfs 이용해서 공통인 부분은 넘기고 공통이 아닌 부분은 삭제or추가 중에 cost 낮은거
2. 공통 부분이 아닌 문자에 대해 그 문자를 제외한 모든 부분을 삭제 or 추가 중에 cost 낮은거
이렇게 해서 가장 cost가 낮게 나온 거를 답으로 출력
이렇게 접근함. 한참만에 풀었는데 시간초과 나와서 빡침. 9퍼에서 나던데.. 고수분들 도와주셈 ㅜㅜ
비용이 어떻게 주어지냐에 따라 LCS를 통한 접근 자체가 최적이 아니게 될 수 있으니까 그냥 DP돌려서 모든 경우중 최적을 구해야됨 - dc App
그러면 중심이 되는 pivot을 하나 잡고 오른쪽에 있는 수를 왼쪽으로 하나씩 넘기면서 전에 계산한 값에서 비용을 따져서 삭제할지 그냥 둘지 복사할지 판단하면 될까요??
pivot을 계속 옮겨 가면서요. 우선 한번 해볼게요 ㄳ요!!
palindrome이라고해서 중심을 잡는다 또는 대칭이다 라는 생각에 묶이게 되는게 이 문제의 트릭같기도 함. 정답보면 좀 허무할수도 있음 - dc App