[BOJ] 2666 : 벽장문의 이동

출처 : https://www.acmicpc.net/problem/2666

전형적인 DP 문제이다.

벽장문이 열리는 경우는 두 가지 경우가 있는데, 닫힌 문과 열린 문을 교환하는 방식으로 생각하면 아래와 같다.

오른쪽에 열린 문과 현재 문을 바꿔주게 할 것인지 아니면 왼쪽에 열린 문과 현재 문을 바꿔주게 할 것인지 이다.

따라서

현재 열린 문을 LD(Left Door), RD(Right Door)라 하고

지금 순서에 열어야 할 문을 CCD(Currently Closed Door)라 하면

점화식은 다음과 같다.

D = min2(abs(CCD-LD)+D(lev+1,CCD,RD), abs(CCD-RD)+D(lev+1,LD,CCD))

소스 코드 : https://github.com/younghk/Problem_Solving/blob/master/BOJ/boj_2666.cpp