백준 14596 Quilting(smaill)

두 패턴의 이미지를 포개면서, 가장 최적의 동선을 통해 부자연스러움의 정도가 가장 낮은 경계를 골라 해당 동선의 부자연스러움의 정도를 출력해야 한다.

문제 드럽게 기네;

일단 여기서 주의해야 할 점은 아래 같은 인덱스거나 +-1 의 경계까지만 움직일 수 있으므로 여기서 가장 주의를 해야한다

그렇다면 맨 위에서부터 가장 최적의 동선을 골라야 할텐데, 이게 어디서 시작하느냐에 따라서도 최적의 경계가 바뀔 수도 있다. 그러므로 해당 문제는 가장 위쪽 모든 인덱스에서 출발하면서 최적의 동선을 가지는 쪽으로 움직여야 하기 때문에 dp로 풀어야 함을 알 수 있다.

그렇다면 시작점을 기준으로 배열을 만든 다음, 해당 시작점에서 가지는 최소의 부자연스러움을 각각 구한다음에 그 중 최소인 부자연스러움 정도를 가지고 오면 된다.