• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

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

23.10.19 20:49 작성 조회수 165

0

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

http://boj.kr/2b3465bfb212482695e3993e7f8ba7f0

 

탑다운으로도 풀어보고 싶어서 시도해봤으나 실패했습니다.

로직에 이상이 있는 것인지, 반례는 어떤 것인지 파악하는 것에 어려움을 겪고 있어 질문 드립니다.

항상 감사합니다!

답변 2

·

답변을 작성해보세요.

0

권창덕님의 프로필

권창덕

질문자

2023.10.23

친절한 답변 감사드립니다.

 

답변의 1번 부분에서 0.5를 더한 이유는 실수 자료형의 정밀도 문제 때문에 100을 곱한 수에 0.5를 더해줬습니다.

 

항상 친절하게 설명해주셔서 공부에 큰 도움이 됩니다. 감사합니다!

 

0

안녕하세요 창덕님 ㅎㅎ

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

		m = 100 * temp + 0.5;
		if (n == 0 && m == 0)
			break;

왜 0.5를 더하신건가요?

 

 

		memset(dp, 0, sizeof(dp));
		cout << dfs(0, 0) << endl; 
  1. 보통의 탑다운은 0부터 시작하지 않습니다.

예산이 주어지면 해당 예산을 지워가는 식으로 -> 감소하면서 이루어져야 합니다.

다만 0으로 초기화하신 것은 정말 잘했습니다. 항상 문제 범위 밖으로 초기화를 하셔야 합니다.

 

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

감사합니다.

강사 큰돌 올림.

채널톡 아이콘