2017년 3월 14일 화요일

2666 벽장문의 이동

백준 2666 벽장문의 이동 https://www.acmicpc.net/problem/2666

문제 설명은 생략한다.
예시에서 2번,5번 벽장이 열려있고 3번,1번,6번,5번 순으로 벽장을 열어야 할 경우를 생각해보면 경우에 대해 표로 나타낼 수 있다.


<>내부에 들어있는 숫자는 벽장을 열어야하는 순서 index이다. (<1>은 3번 벽장, <2>는 1번벽장)
벽장을 순서에 맞게 열 경우마다 그다음 경우는 2가지씩 생긴다. 따라서 완전 탐색을 통해 모든 경우를 따져보면 된다.

DP[N][M] : N번 벽장을 열 때 최소 이동횟수 (M은 열려있는 나머지 벽장 정보)
N번 벽장과 나머지 벽장이 일치하는 경우는 제외하고 경우를 저장하고 이미 열어본적있는 벽장에 대한 정보는 최솟값을 구해 다시 저장하는게 포인트 


#include <cstdio>
#include <algorithm>
using namespace std;
int dp[21][21];        //벽장 순서index, 나머지 벽장번호
int T, op[2];        //벽장 개수, 열려있는 벽장번호(0,1)
int lf,L[21];        //열어야하는 벽장 순서개수, 열어야하는 벽장순서 배열
 
int main(){
    scanf("%d%d%d%d"&T, &op[0], &op[1],&lf);
    for (int n = 1; n <= lf; n++)
        scanf("%d"&L[n]);
    for (int n = 1; n < 21; n++)
        for (int m = 1; m < 21; m++)
            dp[n][m] = -1;
    dp[1][op[1]] = abs(op[0- L[1]);
    dp[1][op[0]] = abs(op[1- L[1]);
 
    for (int n = 1; n < lf; n++){    //algorithm start
        for (int m = 1; m <= T; m++){
            if (dp[n][m] != -1 && L[n] != m){
                int first, second;
                first = dp[n][m] + abs(L[n] - L[n + 1]);
                second = dp[n][m] + abs(m - L[n + 1]);
 
                if (dp[n + 1][m] != -1){
                    first = min(dp[n + 1][m], first);
                }
                if (dp[n + 1][L[n]] != -1){
                    second = min(dp[n + 1][L[n]], second);
                }
                dp[n + 1][m] = first;
                dp[n + 1][L[n]] = second;
            }
        }
    }
    int ans = 987654321;
    for (int n = 1; n <= T; n++){
        if (dp[lf][n] != -1)
            ans = min(ans, dp[lf][n]);
    }
    printf("%d\n", ans);
    return 0;
}
cs

댓글 1개: