백준 14957 - Quilting (Large) (Python)

문제 정보

• https://www.acmicpc.net/problem/14597
• DP

---

문제 정리

두 장의 이미지가 주어질 때, 두 이미지를 최소 2픽셀 이상 겹치도록 경계선을 정해야 한다. 이 때, 경계선을 지나가는 위치에서 두 이미지의 색상이 크게 다르면 합성 결과가 부자연스러워진다.
경계선은 위에서 아래로 한 행씩 내려가며 정해지는데, 현재 행의 경계선 x좌표는 바로 윗 행의 x좌표와 -1, 0, +1 만큼만 차이날 수 있다.

또한, 부자연스러움 정도는 각 행에서 경계선이 선택된 픽셀 위치의 두 이미지 색상 차이를 제곱해 모두 더한 값으로 정의된다.
이 부자연스러움 정도를 최소로 만들어야 한다.

---

풀이

경계선의 이동 규칙이 "위 행에서 -1, 0, 1만큼만 이동 가능" 이므로, 2차원 DP로 최소값을 구할 수 있다.

• DP[i][j] = i행의 경계선이 j열에 있을 때, 부자연스러움 정도의 최소값.

위 점화식을 통해 $O(N^2)$으로 해결할 수 있다.

---

후기

직관적이고 무난한 DP인듯

---

코드

# 백준 14597

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def solve(Y, X, A, B):
    DP = [[0] * X for _ in range(Y)]
    for x in range(X):
        DP[0][x] = (A[0][x]-B[0][x])**2

    for y in range(1, Y):
        for x in range(X):
            cur = (A[y][x]-B[y][x])**2
            prev = DP[y-1][x]
            if x > 0:
                prev = min(prev, DP[y-1][x-1])
            if x < X-1:
                prev = min(prev, DP[y-1][x+1])
            DP[y][x] = cur + prev

    return min(DP[Y-1])


def main():
    Y, X = map(int, input().split())
    A = []
    B = []
    for _ in range(Y):
        A.append(list(map(int, input().split())))
    for _ in range(Y):
        B.append(list(map(int, input().split())))
    print(solve(Y, X, A, B))


main()