글 읽기 - DP 탑다운 memoization 틀림 문제

shinbian11 2년 전 0

탑다운 방식으로 풀었는데요, memoization을 필수적으로 해 줘야 한다고 알고 있어서, 23번쨰 줄처럼 memoization을 해줬는데,

왜 저것을 해주면 답이 틀리고, 안 해주면 답이 맞나요??

#include <bits/stdc++.h>

#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 987654321

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수

int d[100004];
int arr[100004];

int solve(int n) {
	//탑 다운
	if (n == 0) return d[0] = arr[0];
	//if (d[n] != 0) return d[n];  // memoization
	return d[n] = max(arr[n], arr[n] + solve(n - 1));
}

int main()
{
	F_I;
    
	int n, ans = -1e9;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		d[i] = arr[i];
	}

	int a = solve(n - 1);

	for (int i = 0; i < n; i++) {
		ans = max(ans, d[i]);
	}

	cout << ans << '\n';

	return 0;
}

ele99612 1년 전 0

6개월 전이라 아직도 답변을 보실지는 모르겠지만 36번째 줄이 문제로 23번 줄에서 그냥 걸려버립니다. 그래서 안되는 것 같네요.

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

문제

문제

출처

ICPC

DP 탑다운 memoization 틀림 문제

shinbian11 2년 전 0

ele99612 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말