BOJ 2666번: 벽장문의 이동

문제

문제 바로가기> BOJ 2666번: 벽장문의 이동

2666번: 벽장문의 이동

 

풀이

처음에는 3가지 케이스 별로 나누어서 풀었는데,

right 보다 작은 경우는 left 문을 이용하고, left보다 작은 경우는 right 문을 이용하도록 하면

두개의 if문으로 코드를 줄일 수 있었다..! 밑에 그림을 참고하자 :)

+ 추가로 left와 right를 파라미터로 가지고 다니면, 원상태로 복원시켜줄 필요가 없어서 변수관리가 편리하다!

#include<iostream>
#define MAX 25
using namespace std;

int N, M, sl, sr;
int ans=10001;
int order[MAX];

void input(){
    cin >> N;
    cin >> sl >> sr;
    cin >> M;
    for(int i=1; i<=M; i++) cin >> order[i];
}

void solve(int m, int l, int r, int move){
    if(ans <= move) return; // 더 작게 이동하는 방법을 이미 알고 있음
    if(m > M){ // 종료 조건
        ans = move;
        return;
    }
    if(order[m] > l) solve(m+1, l, order[m], move+abs(order[m]-r)); // right 문을 이용
    if(order[m] < r) solve(m+1, order[m], r, move+abs(order[m]-l)); // left 문을 이용
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solve(1, sl, sr, 0);
    cout << ans;
}

 

 

처음 풀이한 코드

#include<iostream>
#define MAX 25
using namespace std;
 
int N, M, ans=10001;
int order[MAX], openDoorIdx[2];
 
void input(){
    cin >> N;
    cin >> openDoorIdx[0] >> openDoorIdx[1];
    cin >> M;
    for(int i=1; i<=M; i++) cin >> order[i];
}
 
void solve(int m, int move){
    if(ans <= move) return; // 더 작게 이동하는 방법을 이미 알고 있음
    if(m == M+1){
        ans = move;
        return;
    }
 
    if(openDoorIdx[0] > openDoorIdx[1]) { // openDoorIdx[0]이 openDoorIdx[1]보다 작음을 보장
        int tmp = openDoorIdx[0];
        openDoorIdx[0] = openDoorIdx[1];
        openDoorIdx[1] = tmp;
    }
 
    if(order[m] < openDoorIdx[0] && order[m] < openDoorIdx[1]){ // use open1 open2
        int tmp = openDoorIdx[0];
        openDoorIdx[0] = order[m];
        solve(m+1, move+tmp-order[m]);
        openDoorIdx[0] = tmp;
    }
    else if(order[m] > openDoorIdx[0] && order[m] > openDoorIdx[1]){ // open1 open2 use
        int tmp = openDoorIdx[1];
        openDoorIdx[1] = order[m];
        solve(m+1, move+order[m]-tmp);
        openDoorIdx[1] = tmp;
    }
    else{ // open1 use open2
        int tmp = openDoorIdx[0];
        openDoorIdx[0] = order[m];
        solve(m+1, move+order[m]-tmp);
        openDoorIdx[0] = tmp;
 
        tmp = openDoorIdx[1];
        openDoorIdx[1] = order[m];
        solve(m+1, move+tmp-order[m]);
        openDoorIdx[1] = tmp;
    }
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solve(1, 0);
    cout << ans;
}