글 읽기 - C++ 동적계획법 시간초과

heon24500 3년 전 0

메모이제이션 적용 했는데, 계속 시간초과가 나네요.. 어디서 잘 못 됐을까요?

#include <iostream>
#include <algorithm>
using namespace std;

#define N 505

int mat[N][N];
int dp[N][N];

int rec(int h, int w) {
	if (w > h) return 0;
	if (h == 1) return mat[1][1];
	if (dp[h][w]) return dp[h][w];
	return dp[h][w] = max(rec(h - 1, w - 1), rec(h - 1, w)) + mat[h][w];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> mat[i][j];
		}
	}

	int max = 0;
	for (int i = 1; i <= n; i++) {
		int ret = rec(n, i);
		if (max < ret) max = ret;
	}
	cout << max;

	return 0;
}

pichulia 3년 전 0

삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

모든 수가 0으로 이루어진 경우 메모이제이션이 안됩니다.

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

문제

문제

출처

ICPC

C++ 동적계획법 시간초과

heon24500 3년 전 0

pichulia 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말