[백준] 2666-벽장문의 이동(C++)

문제링크:www.acmicpc.net/problem/2666

2666번: 벽장문의 이동

 

dp문제입니다.

우선 벽장문을 이동할 때, 가장 가까운 문을 옮기는 그리디적인 방식이 항상 최선이 아니라는 것을 알아야 합니다.

 

ex) 1 0 0 0 1 0 이런식으로 문이 있을때 3번으로 가야한다면 1번문을 이동할건가요? 5번문을 이동할건가요?

 

즉 모든 경우를 다 고려해주어야 합니다. 이때 시간의 효율성을 위해 dp를 사용해야합니다. 

즉, 이전에 방문했던 값을 마킹해두며 진행해야 합니다.

 

 

dp를 사용해야하는 것을 인지했으면, 점화식을 도출해야 합니다.

dp[1번 문위치][2번 문위치][현재 인덱스] = min( 1번 문위치 옮겼을때 최소값, 2번 문위치 옮겼을때 최소값)

이를 토대로 top-down 방식을 사용해서 구현했습니다.

 

 

 

재귀식은 이렇게 구현했습니다.

int solved(int o1, int o2,int cnt) {

	if (cnt == k + 1)
		return 0;

	int &ret = dp[o1][o2][cnt];
	if (ret != -1)
		return ret;
	ret = 0;
	ret = min(abs(arr[cnt] - o1) + solved(arr[cnt], o2, cnt + 1), abs(arr[cnt] - o2) + solved(o1, arr[cnt], cnt + 1));
	return ret;
}

 

 

 

아래는 정답코드입니다.

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

int n = 0, k = 0;
int open1, open2;
int arr[21] = { 0, };
int dp[21][21][21];

int solved(int o1, int o2,int cnt) {

	if (cnt == k + 1)
		return 0;

	int &ret = dp[o1][o2][cnt];
	if (ret != -1)
		return ret;
	ret = 0;
	ret = min(abs(arr[cnt] - o1) + solved(arr[cnt], o2, cnt + 1), abs(arr[cnt] - o2) + solved(o1, arr[cnt], cnt + 1));
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(dp, -1, sizeof(dp));

	cin >> n;
	cin >> open1 >> open2;
	cin >> k;
	for (int i = 1; i <= k; i++)
		cin >> arr[i];

	cout<<solved(open1, open2, 1)<<endl;


	return 0;
}