BOJ 2666 벽장이동

BOJ#2666 벽장문의 이동

풀이법을 몰라서 서핑을 통해서 참조함

[참조 : http://stack07142.tistory.com/157]

* 문제

https://www.acmicpc.net/problem/2666

* 풀이

1. 문제 이해

벽장문을 이동을 열려있는 문이 이동한다는 것으로 바꿔서 생각해봅시다. 훨씬 편하게 문제를 이해할 수 있습니다.

열려있는 문은 항상 2개 뿐이므로 하나를 F, 나머지를 S라고 해봅시다.

열려있는 문이 이동하므로 2가지 경우가 발생합니다. 

1) F가 이동하는 경우

2) S가 이동하는 경우

2. 풀이 설계

이 문제는 벽장문의 사용 순서에 따라 탐색이 진행되고, 완전 탐색이 되어야 합니다.

이 과정에서 필요한 것, 저장시켜야 하는 것, 변화하는 것들을 이용하여 dp를 정의하고 점화식을 세워보면

(정의)

dp[pos1][pos2][idx] : 열린문 F의 위치가 pos1이고 열린문 S의 위치가 pos2 그리고 현재 탐색 위치가 idx일 때, 벽장문을 모두 사용하는데 필요한 최소 이동의 수

(점화식)

dp[pos1][pos2][idx] = min(열린문 F가 이동하는 경우, 열린문 S가 이동하는 경우)

출처: http://stack07142.tistory.com/157 [Hello World]

 D[firstPos][secondPos][idx] = Math.min(

       solve(order[idx], secondPos, idx + 1) + Math.abs((order[idx] - firstPos)),         

       solve(firstPos, order[idx], idx + 1) + Math.abs((order[idx] - secondPos))

       );

[풀이]

import java.io.BufferedReader;

import java.io.FileInputStream;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class boj_2666 {

static int n; // 벽장

static int m; // 사용항 벽장의 개수

static int op[] = new int[2];  // Opened door

static int order[];

static int D[][][] = new int[21][21][21];

public static void main(String[] args) throws IOException {

System.setIn(new FileInputStream("res/input_boj2666.txt"));

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

for (int i = 0; i < 21; i++) {

for (int j = 0; j < 21; j++) {

for (int k = 0; k < 21; k++) {

D[i][j][k] = -1;

}

}

}

n = Integer.parseInt(br.readLine());

StringTokenizer st = new StringTokenizer(br.readLine(), " ");

op[0] = Integer.parseInt(st.nextToken());

op[1] = Integer.parseInt(st.nextToken());

m = Integer.valueOf(br.readLine());

order = new int[m];

for (int i = 0; i < m; i++) {

order[i] = Integer.parseInt(br.readLine());

}

System.out.println(solve(op[0], op[1], 0));

}

static int solve(int firstPos, int secondPos, int idx) {

        // 기저 조건

        if (idx == m) return 0;

        // memoization

        if (D[firstPos][secondPos][idx] != -1) return D[firstPos][secondPos][idx];

        // 탐색

        D[firstPos][secondPos][idx] = Math.min(solve(order[idx], secondPos, idx + 1) + Math.abs((order[idx] - firstPos)),

                solve(firstPos, order[idx], idx + 1) + Math.abs((order[idx] - secondPos)));

        return D[firstPos][secondPos][idx];

    }

}