[python] 백준 2666 벽장문의 이동

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

2666번: 벽장문의 이동

 

문제 해결

• 재귀를 이용해 모든 경우를 해보면서 최적의 해를 출력
• 내 생각에는 함수 구현 문제라고 보는 겻이 편하다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
first, second =map(int,input().split())
m = int(input())
orders = []
dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    orders.append(int(input()))

def solve(x,door1,door2):
    if x ==m:
        return 0
    val = orders[x]
    dp[val][door1][door2] = min(abs(val-door1)+solve(x+1,val,door2), abs(val-door2)+solve(x+1,door1,val))
    return dp[val][door1][door2]
print(solve(0,first,second))