글 읽기 - 10251 운전 면허 시험 질문입니다ㅠㅠ

dustn9401 5년 전 0

메모이제이션 으로 문제를 풀어 봤는데요 ㅠㅠ 시간 초과가 납니다..ㅠㅠ

동적 계획법 이랑 시간 차이는 얼마 안나는 것으로 알고 있는데.. 영문을 모르겠네요 ㅠㅠ

이 문제 이 방법으로는 풀 수 없을까요..?ㅠㅠ

#include <stdio.h>
#include <string.h>
#define INF 1000000000
int n, m, l, g, down[100][100], right[100][100], note[100][100][205][2];
int min(int a, int b) { return a < b ? a : b; };
int memo(int i, int j, int turn, int dir, int cost)
{
	if (cost < 0) return INF;
	if (i == n - 1 && j == m - 1) return 0;
	if (note[i][j][turn][dir] != INF) return note[i][j][turn][dir];
	if (dir) {
		if (j + 1 < m)
			note[i][j][turn][dir] = min(note[i][j][turn][dir], memo(i, j + 1, turn, 1, cost - right[i][j]));
		if (i + 1 < n)
			note[i][j][turn][dir] = min(note[i][j][turn][dir], 1 + memo(i + 1, j, turn + 1, 0, cost - down[i][j]));
	}
	else {
		if (j + 1 < m)
			note[i][j][turn][dir] = min(note[i][j][turn][dir], 1 + memo(i, j + 1, turn + 1, 1, cost - right[i][j]));
		if (i + 1 < n)
			note[i][j][turn][dir] = min(note[i][j][turn][dir], memo(i + 1, j, turn, 0, cost - down[i][j]));
	}
	return note[i][j][turn][dir];
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d%d%d", &n, &m, &l, &g);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m - 1; j++)
				scanf("%d", &right[i][j]);
		for (int i = 0; i < n - 1; i++)
			for (int j = 0; j < m; j++)
				scanf("%d", &down[i][j]);
		for (int i = 0; i < 100; i++)
			for (int j = 0; j < 100; j++)
				for (int k = 0; k < 205; k++)
					for (int l = 0; l < 2; l++)
						note[i][j][k][l] = INF;
		int res = min(memo(0, 0, 0, 0, g), memo(0, 0, 0, 1, g));
		if (res >= INF)
			printf("%d\n", -1);
		else
			printf("%d\n", (n + m - 2)*l + res);
	}
	return 0;
}

qwer9412 5년 전 0

node[i][j][k][l] = INF인 경우가 2가지 일텐데

i,j,k,l에 처음 접근했을 때
절대 갈수 없는 경로일때

2번의 경우에 바로 return 되지 않고 다시 재귀가 돌기때문에 시간초과가 난 것 같습니다. 이 부분도 처리해주면 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

10251 운전 면허 시험 질문입니다ㅠㅠ

dustn9401 5년 전 0

qwer9412 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말