[BOJ 2159 // C++] 케익 배달

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2159번 문제인 케익 배달이다.
문제는 아래 링크를 확인하자.

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

2159번: 케익 배달

\(dp[n][dir]\)를 \(n\)번째 고객까지 배달을 \(n\)번째 고객의 \(dir\)방향에서 마쳤을 때의 배달거리의 최솟값으로 정의하자. 여기서 \(dir\)은 고객이 존재하는 칸 및 고객의 상하좌우칸의 다섯 가지 경우가 존재한다.

 

dp[n][dir]의 값들은 dp[n-1][dir]들 다섯 값을 이용해 항상 계산할 수 있다. 단, dp[1][dir]의 값들은 빵집에서 각 위치로 도착하는 최단거리로 계산한다.

 

위의 점화관계를 구현해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll oldx, oldy, x, y;

ll dpC, dpU, dpD, dpL, dpR;
ll tmpC, tmpU, tmpD, tmpL, tmpR;

ll dist(ll X1, ll Y1, ll X2, ll Y2) {
	return abs(X2 - X1) + abs(Y2 - Y1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	N--;
	cin >> oldx >> oldy >> x >> y;
	dpC = dist(oldx, oldy, x, y), dpU = dist(oldx, oldy, x, y + 1), dpD = dist(oldx, oldy, x, y - 1), dpL = dist(oldx, oldy, x - 1, y), dpR = dist(oldx, oldy, x + 1, y);
	while (N--) {
		oldx = x, oldy = y; cin >> x >> y;
		tmpC = min(dpC + dist(oldx, oldy, x, y), min(min(dpU + dist(oldx, oldy + 1, x, y), dpD + dist(oldx, oldy - 1, x, y)), min(dpL + dist(oldx - 1, oldy, x, y), dpR + dist(oldx + 1, oldy, x, y))));
		tmpU = min(dpC + dist(oldx, oldy, x, y + 1), min(min(dpU + dist(oldx, oldy + 1, x, y + 1), dpD + dist(oldx, oldy - 1, x, y + 1)), min(dpL + dist(oldx - 1, oldy, x, y + 1), dpR + dist(oldx + 1, oldy, x, y + 1))));
		tmpD = min(dpC + dist(oldx, oldy, x, y - 1), min(min(dpU + dist(oldx, oldy + 1, x, y - 1), dpD + dist(oldx, oldy - 1, x, y - 1)), min(dpL + dist(oldx - 1, oldy, x, y - 1), dpR + dist(oldx + 1, oldy, x, y - 1))));
		tmpL = min(dpC + dist(oldx, oldy, x - 1, y), min(min(dpU + dist(oldx, oldy + 1, x - 1, y), dpD + dist(oldx, oldy - 1, x - 1, y)), min(dpL + dist(oldx - 1, oldy, x - 1, y), dpR + dist(oldx + 1, oldy, x - 1, y))));
		tmpR = min(dpC + dist(oldx, oldy, x + 1, y), min(min(dpU + dist(oldx, oldy + 1, x + 1, y), dpD + dist(oldx, oldy - 1, x + 1, y)), min(dpL + dist(oldx - 1, oldy, x + 1, y), dpR + dist(oldx + 1, oldy, x + 1, y))));

		dpC = tmpC, dpU = tmpU, dpD = tmpD, dpL = tmpL, dpR = tmpR;
	}

	cout << min(dpC, min(min(dpU, dpD), min(dpL, dpR)));
}