[백준 시리즈] 2666번 : 벽장문의 이동 - 골드5 / Python

2666번 : 벽장문의 이동

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

사용 알고리즘 : 브루트 포스

 

문제 설명

1. 항상 2개의 문이 열려있는 벽장 N개가 있다.

2. 문을 열 벽장의 순서에 따라서 벽장문 이동 횟수의 최솟값을 구하라.

3. 벽장문은 옆 벽장이 비어있어야 이동가능하다. 

 

제한

시간제한 : 1초 / 메모리 제한 : 128 MB

N (3 <=N <=20)

문을 열 벽장의 개수는 최대 20개이다.

 

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

모든 경우의 수를 고려하는 브루트포스로 문제를 해결했을 때, 최악의 경우에도 20*2^20번의 연산만이 수행되기 때문에 브루트포스 알고리즘으로 해결할 수 있다.

 

2단계 : naive 하게 생각해 보자

현재 더 가까운 쪽의 벽장문을 열더라도 그것이 최선인지는 알 수 없다. 따라서, 주어지는 벽장문마다 열려있는 두 벽장문을 모두 선택해봐야 한다.

 

정답 코드

n = int(input())
a, b = map(int, input().split())
m = int(input())
arr = [int(input()) for _ in range(m)]

def move(a, b, i):
    if i == m:
        return 0
    return min(move(arr[i], b, i+1)+abs(arr[i]-a), move(a, arr[i], i+1)+abs(arr[i]-b))

ans = move(a, b, 0)
print(ans)

 

사견

메모이제이션을 사용하여 최적화할 수 있을 것 같다.