[백준 10251] 운전 면허 시험

문제 링크 => 10251번: 운전 면허 시험 (acmicpc.net)

10251번: 운전 면허 시험

 

다이나믹 프로그래밍 문제이다.

 

아무래도 여러번 recursion을 이용한 memoziation 기법을 이용해서 해결하려고 했으나 시간초과가 계속 뜬다.

그래서 4차원 배열을 설정하여 다음과 같이 해결하였다.

 

dp(curX, curY, turn, direction) = (curX, curY) 에서 turn 번 회전하여 direction 방향을 바라볼 때의 최소 연료량

 

먼저 시작지점에서부터 오른쪽 방향, 아래쪽 방향으로 가는 것은 회전하는 것이 상관 없으므로 이 경우에 대한

테이블을 먼저 채워주고 그 이후에는 다음과 같은 방법으로 테이블을 채웠다.

 

(1) dp(curX, curY, turn, RIGHT) 일 경우 (오른쪽 방향)

     => (curX - 1, curY) 위치에서 (turn - 1) 번 회전했을 때 DOWN 방향에서 들어오는 총 연료량과

           (curX, curY - 1) 위치에서 turn 번 회전할 때 RIGHT 방향에서 들어오는 총 연료량의 최솟값이다.

 

dp[i][j][t][RIGHT]

= min({ dp[i - 1][j][t - 1][DOWN] + down_way[i - 1][j], dp[i][j - 1][t][RIGHT] + right_way[i][j - 1] });

 

 

(2) dp(curX, curY, turn, DOWN) 일 경우 (아랫 방향)

=> (curX - 1, curY) 위치에서 turn 번 회전했을 때 DOWN 방향에서 들어오는 총 연료량과

      (curX, curY - 1) 위치에서 (turn - 1) 번 회전할 때 RIGHT 방향에서 들어오는 총 연료량의 최솟값이다.

 

dp[i][j][t][DOWN]

= min({ dp[i - 1][j][t][DOWN] + down_way[i - 1][j], dp[i][j - 1][t - 1][RIGHT] + right_way[i][j - 1] });

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

int right_way[101][101], down_way[101][101];
int dp[101][101][201][2];
int Row, Col, L, G;
const int RIGHT = 0, DOWN = 1, INF = 1000000000;

int solution()
{
	int min_turn = INF, result;

	// dp(curX, curY, turn_cnt, direction) 
	dp[0][0][0][RIGHT] = dp[0][0][0][DOWN] = 0;
	// 오른쪽
	for (int i = 1; i < Col; i++) {
		dp[0][i][0][RIGHT] = dp[0][i - 1][0][RIGHT] + right_way[0][i - 1];
		dp[0][i][1][DOWN] = dp[0][i - 1][0][RIGHT] + right_way[0][i - 1];
	}
	// 왼쪽
	for (int i = 1; i < Row; i++) {
		dp[i][0][0][DOWN] = dp[i - 1][0][0][DOWN] + down_way[i - 1][0];
		dp[i][0][1][RIGHT] = dp[i - 1][0][0][DOWN] + down_way[i - 1][0];
	}

	// dynamic programming
	for (int i = 1; i < Row; i++) {
		for (int j = 1; j < Col; j++) {
			for (int t = 1; t < Row + Col; t++) {
				dp[i][j][t][RIGHT] = min({ dp[i - 1][j][t - 1][DOWN] + down_way[i - 1][j],
					dp[i][j - 1][t][RIGHT] + right_way[i][j - 1] });
				dp[i][j][t][DOWN] = min({ dp[i - 1][j][t][DOWN] + down_way[i - 1][j],
					dp[i][j - 1][t - 1][RIGHT] + right_way[i][j - 1] });
			}
		}
	}

	for (int t = 0; t < Row + Col; t++) {
		if (dp[Row - 1][Col - 1][t][RIGHT] <= G) {
			min_turn = min(min_turn, t);
		}
		if (dp[Row - 1][Col - 1][t][DOWN] <= G) {
			min_turn = min(min_turn, t);
		}
	}

	result = min_turn + L * (Row + Col - 2);
	return result >= INF ? -1 : result;
}

void set_drive()
{
	int i, j;

	scanf("%d %d %d %d", &Row, &Col, &L, &G);
	for (i = 0; i < Row; i++) {
		for (j = 0; j < Col - 1; j++) {
			scanf("%d", &right_way[i][j]);
		}
	}
	for (i = 0; i < Row - 1; i++) {
		for (j = 0; j < Col; j++) {
			scanf("%d", &down_way[i][j]);
		}
	}
}

void initialize()
{
	int i, j, k;
	for (i = 0; i <= Row; i++) {
		for (j = 0; j <= Col; j++) {
			for (k = 0; k <= 200; k++) {
				dp[i][j][k][DOWN] = dp[i][j][k][RIGHT] = INF;
			}
		}
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		set_drive();
		initialize();
		printf("%d\n",solution());
	}

	return 0;
}