7-I 탑다운 방식 질문드립니다.

안녕하세요 창덕님 ㅎㅎ

일단 이부분이 좀 이상한데요.

		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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

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