# Driving License

# 문제

 

# 입력 및 출력

 

 

# 풀이

어처피 회전 횟수를 제외하면 세로 M-1, 가로 N-1칸씩 이동하는 것은 정해져 있다.

따라서 L * {(M-1) + (N-1)}은 고정이고 여기에 회전 횟수만 최소로 해서 더해주면 결과 값을 구할 수 있다.

 

문제는 연료이다.

주어진 연료 G 이하로 사용하면서 회전 횟수를 최소로 만들어야 한다.

 

처음엔 pair을 사용해서 하려다가 너무 복잡해지기도 하고 접근이 힘들어져서 4차원 배열을 선택했다.

dp[x][y][k][l] => (x, y) 좌표에서 회전수가 k번이고, 방향은 l일 때의 최소 연료 합

 

일단 (x,y) 좌표에서 회전수는 max(x, y) * 2를 절대 넘지 않는다.

예) (2,2) 에서는 최대 3번, (2,4) 에서는 최대 4번, (3,3) 에서는 최대 5번 

따라서 max(x,y) * 2 만큼 반복하면 널널하게 확인할 수 있다.

 

이제 방향을 확인해야 한다.

오른쪽으로 가는 경우를 0으로 두고, 아래로 가는 경우를 1로 둔다.

1) 오른쪽으로 가는 경우 (방향이 0 인 경우)

-> ㄴ, ㅡ 방향이 있다.

이 경우는 dp[i][j][k][0] = min(dp[i][j-1][k-1][1], dp[i][j-1][k][0]) + hor[i][j-1]

2) 아래쪽으로 가는 경우 (방향이 1인 경우)

-> ㄱ, ㅣ 방향이 있다.

이 경우는 dp[i][j][k][1] = min(dp[i-1][j][k-1][0], dp[i-1][j][k][1]) + ver[i-1][j]

 

이렇게 dp 값을 채우고 나서는 (M-1, N-1) 좌표에서 연료 합이 G 이하이면서 최소 회전 수를 가지는 경우를 찾으면 된다.

자세한 부분은 주석을 참고하도록!

#include <fstream>
#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

ifstream fin("drive.inp");
ofstream fout("drive.out");

int dp[101][101][202][2]; // [r][c][rotation time][direction] => (r,c) 위치에서 회전수가 rotation time 일 때 최소 fuel
int hor[101][101]; // fuel of horizontal segment
int ver[101][101]; // fuel of vertical segment

// hor, ver 배열 입력받음
void input(int m, int n) { 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n - 1; j++) {
			fin >> hor[i][j];
		}
	}
	for (int i = 0; i < m - 1; i++) {
		for (int j = 0; j < n; j++) {
			fin >> ver[i][j];
		}
	}
}

// dp INF 값으로 초기화 및 1번이라도 회전하면 갈 수 없는 부분 초기화
void init(int m, int n) { 
	int max_turn = max(m, n) * 2; // 회전 수 상한 값
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < max_turn; k++) {
				dp[i][j][k][0] = dp[i][j][k][1] = INF;
			}
		}
	}
	dp[0][0][0][0] = dp[0][0][0][1] = 0; // (0,0)
	for (int i = 1; i < n; i++) { // [0][~]
		dp[0][i][0][0] = dp[0][i - 1][0][0] + hor[0][i - 1];
	}
	for (int i = 1; i < m; i++) { // [~][0]
		dp[i][0][0][1] = dp[i - 1][0][0][1] + ver[i - 1][0];
	}
}

void make_dp(int m, int n) {
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			int max_turn = max(i, j) * 2;
			for (int k = 1; k < max_turn; k++) {
				// [i][j][k][0](오른쪽) : ㄴ, ㅡ 방향 (회전하는 경우, 회전하지 않는 경우)
				dp[i][j][k][0] = min(dp[i][j - 1][k - 1][1], dp[i][j - 1][k][0]) + hor[i][j - 1];
				// [i][j][k][1](아래) : ㄱ, ㅣ 방향
				dp[i][j][k][1] = min(dp[i - 1][j][k - 1][0], dp[i - 1][j][k][1]) + ver[i - 1][j];
			}
		}
	}
}

// 주어진 fuel 값을 만족하는 최소 회전 수를 찾음
int find(int m, int n, int fuel, int time) {
	int max_turn = max(n, m) * 2;
	for (int k = 0; k < max_turn; k++) {
		if (dp[m - 1][n - 1][k][0] <= fuel || dp[m - 1][n - 1][k][1] <= fuel) {
			return time * (m - 1 + n - 1) + k;
		}
	}
	return -1;
}

int main() {
	int T, M, N, L, G;
	fin >> T;
	while (T--) {
		fin >> M >> N >> L >> G;
		input(M, N);
		init(M, N);
		make_dp(M, N);
		int result = find(M, N, G, L);
		fout << result << "\n";
	}
}

 

처음엔 3차원 배열로 풀었다가 4차원으로 합칠 수 있을 것 같아서 합쳤다