글 읽기 - 77퍼에서 시간초과가 납니다 ㅜㅜ

tkdgns685 4년 전 0

dp 로 풀었는데 시간초과가 나네요. 혹시 다른 풀이가 있을까요?

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;

#define inf 10000000000
typedef long long ll;
vector<vector<int>> v;
vector<vector<ll>> dp;
int n, m, d;

ll solve(int a, int b) {
	if (a >= n) return 0;

	ll &ref = dp[a][b];
	if (ref) return ref;

	int q , w;
	
	ref = -inf;
	for (int i = a + 1; i <= a + d; i++) {

		q = (b - d + i - a < 0 ? 0 : b - d);
		w = (b + d - (i - a) >= m ? m - 1 : b + d);

		for (int k = q; k <= w; k++) {
			if (i - a + abs(k - b) <= d) {
				if (i <= n - 1) {
					ref = max(ref, solve(i, k) + v[i][k] * v[a][b]);
				}
			}
		}
	}
	if (ref == -inf) ref = 0;
	return ref;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 cin >> n >> m >> d;

	v.resize(n + 1);
	dp.resize(n + 1);

	for (int i = 0; i < n; i++) dp[i].resize(m);
	
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < m; k++) {
			int a; cin >> a;
			v[i].push_back(a);
		}
	}

	ll res = -inf;

	for (int i = 0; i < m; i++) {
		res = max(res, solve(0, i));
	}
	cout << res << "\n";
}

tkdgns685 4년 전 0

확실히 for 문이 재귀보다 빠르네요. 똑같은 코드인데도 속도 차이가 상당히 나네요 ㅜㅜ

djm03178 4년 전 1

똑같은 코드가 아니니까 차이가 크게 납니다.

범인은 18번째 줄입니다. 실제로 계산된 결과가 0이라면 dp[a][b]에 0이 들어갈 텐데, 아직 방문을 안 한 것과 결과값이 실제로 0인 것을 구분하지 못하기 때문에 재탐색을 들어가게 됩니다.

tkdgns685 4년 전 0

그렇네요 ㅋㅋ 음수까지 되는데도 0 을 고려하지 않았네요. 수정하니까 재귀도 잘 통과됩니다.

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

문제

문제

출처

ICPC

77퍼에서 시간초과가 납니다 ㅜㅜ

tkdgns685 4년 전 0

tkdgns685 4년 전 0

djm03178 4년 전 1

tkdgns685 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말