인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

먼저 hp가 0이하일 때 해당 정점은 무시가 되어야 합니다. 즉, 0이 아니라 -INF를 주어서 해당 경우의 수를 없애는게 중요합니다.

int go(int idx, int hp) {
	if (hp <= 0) {return -INF;}

이렇게 매개변수로 happy를 만들어서 집어넣게 되면 local optimum이 만들어지지 않습니다.

이런식으로 코드를 짜야 합니다. 이래야 로컬 옵티멈이 잘만들어지는데요.

	ret = max(go(idx + 1, hp), go(idx + 1, hp - piro[idx]) + happy[idx]);

이게... 설명하자면 이렇습니다. 함수호출해서 DP를 만들어나가는데 마지막에 180반환하고 그게.. 올라오는 형태가 되겠죠? 그래서 해당 DP에는 각각 이런 값들만이 쌓이게 됩니다. 즉, 올바르게 local optimum이 안쌓여지게 되는 것이죠.

제가 한번 다듬어 봤는데요. ㅎㅎ 참고부탁드립니다. (이렇게 하면 통과뜹니다.)

#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;
int dp[21][101];
int n;
vector<int> piro, happy; 

int go(int idx, int hp) {
	if (hp <= 0) {return -INF;}
	if (idx == n) {return 0;}
	int &ret = dp[idx][hp];
	if (ret != -1) {return ret;}
	ret = max(go(idx + 1, hp), go(idx + 1, hp - piro[idx]) + happy[idx]);
	return ret;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	int x;
	for (int i = 0; i < n; i++) {
		cin >> x;
		piro.push_back(x);
	}
	for (int i = 0; i < n; i++) {
		cin >> x;
		happy.push_back(x);
	}
	memset(dp, -1, sizeof(dp));
	cout << go(0, 100, 0) << endl;
}

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

shhmun02님, 코드에 문제가 발생했을 때는 해당 부분을 천천히 살펴보셔야 해요. 재귀 함수를 사용할 때는 기저 조건(base case)이 올바르게 구현되었는지, 각 재귀 호출에서 상태가 올바르게 업데이트되며, 메모이제이션(Memoization)을 하셨다면 그 과정에서 오류가 없는지 검토해야 합니다.

행복(hppy) 값을 반환하는 부분에서도 최대값이 올바르게 선택되고 있는지, 그리고 모든 가능한 경우를 잘 고려하고 있는지 확인해 보세요. 저희가 코드를 직접 볼 수 없으니, shhmun02님이 작성하신 코드를 기반으로 이런 점들을 다시 한 번 살피는 것이 좋겠습니다.

또한, 백준 온라인 저지(BOJ) 사이트에서 해당 문제에 대한 질문 게시판을 둘러보는 것도 도움이 될 수 있습니다. 때로는 다른 사람들이 비슷한 문제를 겪었는지, 해결 방법이 공유되었는지 확인해보는 것이 좋습니다.

정답이 되지 않는 경우에는 입력 값을 다양하게 변경해보며 예외 상황을 찾아보시고, 디버깅을 해보는 것도 좋은 방법입니다. 가능하다면 코드를 디버거로 한 줄씩 실행해보며 변수의 변화를 관찰하는 것도 큰 도움이 될 것입니다.

이상으로 도움을 드릴 수 있는 부분은 여기까지이고, 만약 이후에도 해결이 안된다면 해당 강의의 커뮤니티에 질문을 올려 강사님의 도움을 받아보시는 것을 추천드립니다.

모든 질문은 강의의 커뮤니티 질문&답변 게시판을 통해 강사님께서 직접 확인하시게 되므로, 거기에 문의하시면 더 구체적이고 상세한 답변을 받으실 수 있을 것입니다.

문제 해결을 위해 행운을 빕니다!