백준 2666 벽장문의 이동 C++풀이 - DP

현상금 사냥꾼 김정은 문제와 유사하다.

DP 배열을 이용하고, dp[i][j] 는 첫 번째 벽장이 i 번 자리로 이동하고

두 번째 벽장이 j 번 자리로 이동했을 때, 

남은 것을 수행하는는데 필요한 최소 거리를 뜻한다.

 

즉 dp[0][0]이면 처음 자리에서 모든 쿼리를 다 해결했을 때 최소 거리가 나온다.

 

점화식은 다음처럼 유도했다.

dp[0][0] = min( dp[1][0] + dist(0->1) , dp[0][1] + dist(0->1) )

...

next = max(i, j) + 1;

dp[i][j] = min(dp[next][j] + dist(i->next) , dp[i][next] + dist(j->next) );

 

초기값은 i, j 가 마지막 질문을 받았을 때, 그 자리로 이동하는 거리만 return 해주면 된다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int n, s1, s2,q;
int obj[21];
int dp[21][21];
int abs(int x) {
	if (x > 0) return x;
	return -x;
}

int query(int c1, int c2, int s1, int s2) {
	if (c1 == q) {
		return dp[c1][c2]=abs(s1 - obj[q]);
	}
	else if (c2 == q) {
		return dp[c1][c2] = abs(s2 - obj[q]);
	}

	if (dp[c1][c2]) return dp[c1][c2];
	
	int next = max(c1, c2)+1;
	int p = query(c1, next, s1, obj[next]) + abs(s2-obj[next]);
	int q = query(next, c2, obj[next], s2)+ abs(s1 - obj[next]);
	
	return dp[c1][c2] = min(p, q);

}

int main() {
	scanf("%d", &n);
	scanf("%d %d", &s1, &s2);
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) {
		scanf("%d", &obj[i]);
	}
	query(0, 0, s1, s2);
	printf("%d\n", dp[0][0]);


}