C++[BOJ] 백준 10251번 운전 면허 시험

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

10251번: 운전 면허 시험

---

SOLUTION

4차원 dp 배열을 잡았는데 각각의 의미는
[grid에서의 x좌표][grid에서의 y좌표][현재 방향(0=왼쪽→오른쪽, 1=위→아래)][여기까지 오는데 방향이 바뀐 횟수]
다음과 같다.

각각의 행에서는, 예를들어 2번째 행에 있는 모든 node들은 2*2 = 4번 안에 접근이 가능하다.
손으로 그려보면 3행은 6번, 4행은 8번...임을 알 수 있고, 여기서 n행은 n*2회안에 접근이 가능하다는 것을 유추할 수 있다.
(그래서 6번째 반복문 안에서 k가 i*2+1까지만 돌았음)

0행과 0열은 미리 초기화를 시켜놓고 (1,1)위치부터 반복문을 돌면서 dp 배열을 채워주기 시작했다.
0행, 0열은 모두 다 방향 전환 없이 접근이 가능하기 때문에 방향전환 횟수는 0 으로 고정시켜 초기화를 했다.
1행 1열부터는 유도되는 일반식으로부터 값을 채웠다.
ex) 3행 3열에 2번의 방향전환으로 도착했고, 마지막 방향은 위→아래인 경우(dp[3][3][2][1])에는
(2,3)에 한 번의 방향전환으로 도착했고, 마지막 방향이 왼쪽→오른쪽인 경우 + Down[2][3]과
(2,3)에 두 번의 방향전환으로 도착했고, 마지막 방향이 위→아래인 경우 + Down[2][3] 중 더 작은 값이 들어가게 된다.

위와 같은 방식으로 dp 배열을 초기화하고 난 후, 답을 얻고자 할 때는 dp[M-1][N-1]에 모든 가능한 방향전환 횟수(0~200)만에 위→아래 혹은 왼쪽→오른쪽으로 도착한 경우 중에 G보다 작거나 같은 경우에 미리 무한대로 초기화해 준 ans를 갱신해준다.
여기서, (M-1,N-1)까지 도달하기 위해서는 간선을 (M-1)+(N-1)번 무조건 지나야 하기 때문에 (M - 1) + (N - 1)) * L + i 식이 유도된다.
만약 ans에 여전히 무한대의 값이 들어가있다면 G보다 작거나 같은 수가 없다는 것이니까 -1을 초기화해준다.

처음에는 3차원으로 끄적끄적대고 4차원을 쓰겠다는 생각을 전혀 못했는데, 4차원 배열을 쓴다는 힌트를 듣고부터 문제가 술술 풀렸다.
뭔가 코드가 엄청 짧아질 것 같아서 최대한 줄 수를 줄여보려고 중괄호 생략 가능한데는 전부다 생략하고 한줄에 들어갈 수 있겠다 싶으면 다 한줄에 넣음ㅋㅎㅋㅎ

---

코드

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int Right[101][101], Down[101][101], dp[101][101][2][201]; //1행 - 최대2, 2행 - 최대4, 3행 - 최대 6 ... 100행 - 최대200
int main() {
	//ifstream in("drive.inp");
	//ofstream out("drive.out");
	int tc;
	cin >> tc;
	while (tc--) {
		int  M, N, L, G, ans = 123456789;
		cin >> M >> N >> L >> G;
		for (int i = 0; i < M; i++) for (int j = 0; j < N - 1; j++) cin >> Right[i][j];
		for (int i = 0; i < M - 1; i++) for (int j = 0; j < N; j++) cin >> Down[i][j];
		for (int i = 0; i < 101; i++) for (int j = 0; j < 101; j++) for (int k = 0; k < 2; k++) for (int l = 0; l < 201; l++) dp[i][j][k][l] = 123456789;
		dp[0][0][0][0] = 0; dp[0][0][1][0] = 0;
		for (int i = 1; i < M; i++) dp[i][0][1][0] = dp[i - 1][0][1][0] + Down[i - 1][0];
		for (int i = 1; i < N; i++) dp[0][i][0][0] = dp[0][i - 1][0][0] + Right[0][i - 1];
		for (int i = 1; i < M; i++) for (int j = 1; j < N; j++) for (int k = 1; k < i * 2 + 1; k++) {
			dp[i][j][0][k] = min(dp[i][j - 1][1][k - 1] + Right[i][j - 1], dp[i][j - 1][0][k] + Right[i][j - 1]); dp[i][j][1][k] = min(dp[i - 1][j][0][k - 1] + Down[i - 1][j], dp[i - 1][j][1][k] + Down[i - 1][j]);
		}
		for (int i = 0; i < 201; i++) if (dp[M - 1][N - 1][0][i] <= G) ans = min(ans, ((M - 1) + (N - 1)) * L + i); else if (dp[M - 1][N - 1][1][i] <= G) ans = min(ans, ((M - 1) + (N - 1)) * L + i);
		if (ans != 123456789) cout << ans << '\n'; else cout << -1 << '\n';
	}
}