인프런 커뮤니티 질문&답변
작성한 질문수
7-L 재귀적 풀이 질문있습니다.
해결된 질문
작성
·
102
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요 선생님
해당 문제를 재귀적으로 풀고 테스트케이스 모두 통과하는데 틀렸다고 나옵니다..
혹시 어떤 부분이 잘못됬는지 봐주시면 감사하겠습니다.
퀴즈
동적 계획법(Dynamic Programming)을 적용하기 위한 주요 조건은 무엇일까요?
탐욕적 선택 속성, 최적 부분 구조
최적 부분 구조, 중복되는 부분 문제
중복되는 부분 문제, 결정론적 결과
탐욕적 선택 속성, 메모이제이션
답변 1
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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
http://boj.kr/9bfc9acb4d6549d38e354b8c9cf6e44d
입니다. 감사합니다