7-L 재귀적 풀이 질문있습니다.

2024-10-28T06:50:02.742Z

0

http://boj.kr/9bfc9acb4d6549d38e354b8c9cf6e44d

입니다. 감사합니다

0

안녕하세요 ㅎㅎ

이렇게 매개변수로 J를 넘기는 경우 경우의 수가 n까지 흘러갔을 때의 그 경로를 기반으로 max를 채우게 되어서 중간단계의 DP가 채워지지 않고 있으며 그로인한 UB가 발생해서 틀리는 것입니다.

	return ret = max(go(num + 1, hp - L[num], happy + J[num]), go(num + 1, hp, happy));

이를 J[num]을 밖으로 빼서 max값을 비교하는 것으로 만들어야 합니다.

디버깅을 해볼까요?

예를 들어

3
1 21 79
20 30 25

라는 입력의 경우.

2 : 99 일 때는 25가 나와야 합니다.

num 2부터 시작하고 -> 체력이 99남았을 때 최댓값은 25이기 때문입니다.

그러나 정원님의 코드를 디버깅해보시면 -> 45가 나옵니다.

즉, 제대로 채워지지 않고 있습니다.

디버깅코드는 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
int n,L[21],J[21],dp[21][101];
int go(int num, int hp,int happy) {
	if (hp <= 0) return 0;
	if (num == n) return happy;
	int& ret = dp[num][hp];
	if (ret != -1) return ret;
	ret = 0; 
	ret = max(go(num + 1, hp - L[num], happy + J[num]), go(num + 1, hp, happy));
	cout << num << " : " << hp << '\n';
	cout << ret << '\n';
	return ret;   
}
int main() {
	cin >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		cin >> L[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> J[i];
	}
	cout << go(0, 100,0);
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.