23.10.19 20:49 작성
·
196
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
http://boj.kr/2b3465bfb212482695e3993e7f8ba7f0
탑다운으로도 풀어보고 싶어서 시도해봤으나 실패했습니다.
로직에 이상이 있는 것인지, 반례는 어떤 것인지 파악하는 것에 어려움을 겪고 있어 질문 드립니다.
항상 감사합니다!
답변 2
0
2023. 10. 23. 17:32
친절한 답변 감사드립니다.
답변의 1번 부분에서 0.5를 더한 이유는 실수 자료형의 정밀도 문제 때문에 100을 곱한 수에 0.5를 더해줬습니다.
항상 친절하게 설명해주셔서 공부에 큰 도움이 됩니다. 감사합니다!
0
2023. 10. 20. 17:10
안녕하세요 창덕님 ㅎㅎ
일단 이부분이 좀 이상한데요.
m = 100 * temp + 0.5;
if (n == 0 && m == 0)
break;
왜 0.5를 더하신건가요?
memset(dp, 0, sizeof(dp));
cout << dfs(0, 0) << endl;
보통의 탑다운은 0부터 시작하지 않습니다.
예산이 주어지면 해당 예산을 지워가는 식으로 -> 감소하면서 이루어져야 합니다.
다만 0으로 초기화하신 것은 정말 잘했습니다. 항상 문제 범위 밖으로 초기화를 하셔야 합니다.
idx + 1과 idx를 넘겨서 모든 경우의 수를 따진 것은 잘하셨습니다.
dp[price] = max(dfs(idx + 1, price), dfs(idx, price + arr[idx].second) + arr[idx].first);
그러나.
보통의 DP함수는 매개변수의 수 = 배열의 차원의 수가 되어야 합니다.
예를 들어.
dp(0, 1) -> dp[0][1] -> dp(0, 2) ... dp (0, 3)
이렇게 되는게 기본형식이고 dp(0, 1)은 다시 호출될일이 없지요. 그리고 나서 dp[0][1]이 쌓여져서 만들어집니다.
근데 창덕님 코드를 보시면.
dp(1, 200) -> dp[200]
이후에 이런 함수가 실행되지 않을까요?
dp(3, 200) -> dp[200]
그래서 먼저 dp(1, 200)가 되었더라도 dp(3, 200)에서 다시 갱신되어야 하는데 메모이제이션 로직 때문에 갱신이 안되는 그런 꼬이는 현상이 발생되지 않을까요?
제가 한번 다시 탑다운풀이를 짜봤는데요. 참고 부탁드립니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100004;
int n, m1, m2, c;
int items[MAXN], prices[MAXN];
int memo[MAXN];
int dp(int budget) {
if (budget < 0) return INT_MIN;
if (budget == 0) return 0;
if (memo[budget] != -1) return memo[budget];
int best = 0;
for (int i = 0; i < n; i++) {
if (budget - prices[i] >= 0) {
best = max(best, items[i] + dp(budget - prices[i]));
}
}
memo[budget] = best;
return best;
}
int main() {
while (1) {
scanf("%d %d.%d", &n, &m1, &m2);
if (n == 0) break;
int cost = m1 * 100 + m2;
for (int i = 0; i < n; i++) {
scanf("%d %d.%d", &c, &m1, &m2);
items[i] = c;
prices[i] = m1 * 100 + m2;
}
memset(memo, -1, sizeof(memo));
printf("%d\n", dp(cost));
}
return 0;
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.