벽장문의 이동(DP)

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

2666번: 벽장문의 이동

 

기본적으론 완전 탐색을 기반으로 두고

이미 탐색했던 상황에 대해선 저장된 값을 사용하는 DP 기법을 활용하는 문제다.

 

처음엔 특정 문을 열때 각각 왼쪽, 오른쪽에 있는 벽장으로부터 열 수 있다는 점에서 착안하여 DP[21][2]의 이중 어레이를 사용하려고 했다.

하지만 특정 벽장을 열때마다, 즉 단계마다 열려있는 벽장의 정보를 저장할 수가 없었다.

 

해당 문제에서 중요한 점은 각 상황에 따라 열려있는 벽장이 달라진다는 점이다.

모든 상황을 염두에 두는 완전 탐색을 진행할 것이므로 DP의 인덱스로 '상황(단계)'과 '열려있는 두 문'을 사용한다.

 

DP[k][i][j] = k번째 단계에서 i, j 방이 열려있을 때 벽장문을 전부 사용하는데 필요한 최소 이동값

 

이 상황에서 앞서 말한 왼쪽, 오른쪽에 있는 벽장으로부터 여는 상황을 비교하여 더 작은 값을 찾도록 한다.

a번째 벽장문이 열려있을 때 b의 벽장문을 열고싶다면 abs(a - b)의 이동값을 갖게 된다.

 

#include <iostream>
#include <cstring>
using namespace std;

int DP[21][21][21];
// DP[k][i][j] = k번째 단계에서 i, j방이 열려있을때
// 벽장문을 전부 사용하는데 필요한 최소 이동값
int N, len;
int dest[21];

int DFS(int step, int x, int y)
{
	if (step >= len + 1) return 0; // step을 넘어가면 0을 반환
	if (DP[step][x][y] != -1) return DP[step][x][y]; // 이미 저장된 값이 있으면 사용

	int next = dest[step];
	DP[step][x][y] = min(
		abs(x - next) + DFS(step + 1, next, y), 
		abs(y - next) + DFS(step + 1, x, next)
	);
	return DP[step][x][y];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int op1, op2;
	cin >> N >> op1 >> op2 >> len;

	for (int i = 1; i <= len; i++)
	{
		cin >> dest[i];
	}

	memset(DP, -1, sizeof(DP));
	cout << DFS(1, op1, op2);
}