BOJ 2666

08 Apr 2020 • ProblemSolving

벽장문의 이동

문제출처

문제 해석

  • 두개의 열린 문이 주어졌을 때, M개의 문을 여는데 필요한 문의 최소 이동 수를 구하는 문제입니다.

설계(20)

  • DP를 사용하는 문제입니다.
  • 처음에 N<=20 인것을 고려하여 점화식을 “D[state][i] = state상태에서 i번째 문을 열기 위해서 필요한 최소 이동 수”로 설정하였습니다.
  • 메모리제한이 128MB로 위의 배열을 설정할 수 있을 것 같습니다.
  • 먼저, 주어진 두개의 문을 1로 하는 비트를 선언합니다. (1«(N-door1)+1«(N-door2))
  • 하나의 문을 이동시키기 위해서 모든 열려있는 문과의 거리의 최소값을 갱신하도록 하였습니다.
  • 이와 동시에 문의 상태도 갱신합니다.
  • 위의 점화식으로 구현이 가능한 것을 보였습니다. 다만, 메모리 소모가 극심하여서 최적화가 필요할 것으로 보입니다.
  • 열려있는 문이 두개로 정해져있기 때문에 굳이 문의 상태를 점화식에 표현하지 않아도 될 것 같습니다.
  • 점화식을 다음과 같이 변경하였습니다.
    • D[i][door1][door2] = “첫번째문이 door1이고, 두번째 문이 door2인 상태에서 i번째 문을 열기 위한 최소 이동수”
  • 1번문으로 갈 경우와 2번문으로 갈 경우 두가지 조건의 최소값을 찾습니다.

구현1 (30)

코드
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN (1<<20)+1
#define INF 987654321
int cache[MAXN][21];
int arr[21];
int N,M;
int dp(int state, int cur){
    if (cur ==M) return 0;
    int& ret = cache[state][cur];
    if (ret !=-1) return ret;
    ret = INF;
    // 벽장문이 열려있는 곳으로 가기위한 최소이동수
    for (int i = 0; i < N; i++){
        if (state&(1<<i)){
            int next_state = state;
            next_state &= ~(1<<i);
            next_state |= 1<<(N-arr[cur]);
            ret = min(ret,dp(next_state,cur+1)+abs((N-i)-arr[cur]));
        }
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(cache,-1,sizeof(cache));
    int state = 0;
    int a,b;
    cin >> N >> a >> b;
    state += (1<<(N-a))+(1<<(N-b));
    cin >> M;
    for (int i = 0; i < M; i++){
        cin >> arr[i];
    }
    cout << dp(state,0);
    return 0;
}
코드2(최적화)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 21
#define INF 987654321
int cache[MAXN][MAXN][MAXN];
int arr[21];
int N,M,door1,door2;
int dp(int cur, int door1, int door2){
    if (cur ==M) return 0;
    int& ret = cache[cur][door1][door2];
    if (ret !=-1) return ret;
    ret = INF;
    // 1번문으로 가는 경우
    ret = min(ret,dp(cur+1,arr[cur],door2)+abs(door1-arr[cur]));
    // 2번문으로 가는 경우
    ret = min(ret,dp(cur+1,door1,arr[cur])+abs(door2-arr[cur]));
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(cache,-1,sizeof(cache));
    int state = 0;
    cin >> N >> door1 >> door2;
    cin >> M;
    for (int i = 0; i < M; i++){
        cin >> arr[i];
    }
    cout << dp(0,door1,door2);
    return 0;
}
디버깅
  • 첫번째 DP를 구현할 때, 상태의 MAX값을 1«20+1로 설정하는 실수를 하였습니다.
  • ”+”의 우선순위가 높아서 1«21의 공간을 설정한 셈이 됩니다. 이렇게 할 경우 메모리 초과가 발생하였습니다.
제출결과
  • 코드1 (88MB,48 ms), 코드2 (2020KB, 0 ms)

마무리

  • 저의 가장 취약한 부분인 DP를 연습하기에 아주 좋은 문제였습니다.
  • 만약 열려있는 문이 여러개일 경우에 코드1의 방법으로 구현하는게 더 낫지 않을까 생각해봅니다.
 BOJ

Related Posts