[도전 19일차] KOI 벽장문의 이동 풀이

※복습 : 

문제 : 백준 2666 벽장문의 이동

문제 링크

 

사용 알고리즘 : 백트래킹

 

풀이: 

벽장에서 n가지 벽장문 중 오직 2가지 문을 이용할 수 있다. 이때 2가지 문을 제외한 n-2가지 문들은 어떤 칸막이로 덮여 있는데, 이 칸막이들을 적당히 움직여 다른 문들도 이용할 수 있다. (그때마다 2가지)

현재 칸막이의 위치와 앞으로 이용하고 싶은 문들의 순서가 주어질 때 칸막이를 가장 적게 움직이고서 문들을 순서대로 모두 사용하는 것이 목표다.

 

n이 20이하로 작으므로 가능한 모든 경우를 탐색하는 것이 가능하다.

이제 사용할 수 있는 문 중 왼쪽에 있는 것을 A 문, 오른쪽에 있는 것을 B문으로 하자.

내가 만약 k번째 문을 사용하고 싶다면 A문과 B문 중 하나를 사용해야 하는데, 사용해야 할 문은 여러개이므로 A문과 B문을 움직인 후의 상태를 모두 고려해 최솟값을 구해야만 답이 될 수 있다.

 

코드

#include<stdio.h>
#include<algorithm>
using namespace std;
int n,a,b,m,arr[21];
int solve(int k,int a,int b){
    if(k>m)
        return 0;
    int x=0,y=0,a_=a,b_=b;
    if(k>0)
        x=abs(a-arr[k]),y=abs(b-arr[k]),a_=arr[k],b_=arr[k];
    return min(x+solve(k+1,a_,b),y+solve(k+1,a,b_));
}
int main(){
    scanf("%d%d%d%d",&n,&a,&b,&m);
    for(int i=1;i<=m;i++)
        scanf("%d",arr+i);
    printf("%d",solve(0,a,b));
}

코드 개선 힌트 : a<b 일 때 만약 arr[k] < a라면 탐색공간의 배제가 가능하다.

 

궁금한 점이 있으시다면 질문 남겨주세요 :)