coins 재귀 및 dp 질문

  • 보다라닥
    보다라닥

    기본 완전탐색에서 dp를 추가했는데 이상한 답만 뜨네요... 일주일째 고민중인데도 모르겠습니다...ㅠㅠㅠ

    코인이 큰 순서대로 남은 돈(left)에서 빼고 재귀를 계속 호출해 0이 나오면 방법을 하나 찾았다고 보고 리턴합니다.
    dp는 남은 돈 기준으로 하여 150원이 남았다고 하면 이를 cache 배열에서 찾아 이전정보가 있으면 그를 리턴합니다.

    이하는 코드입니다. 도와주시면 감사하겠습니다....ㅠㅠ

    #include <stdio.h>
    #include <string.h>
    int coin[110];
    int m, c;
    int cache[5010];
    
    int howMany(int forward,int left) {
        int ans = 0;
        if (left == 0) return 1;
        for (int i = forward; i >=0 ; i--) {
            if (left >= coin[i]) {
                if (cache[left] != -1) return cache[left];
                left = left - coin[i];
                ans += howMany(i, left);
                cache[left] = ans;
                left = left + coin[i];
            }
        }
        return ans;
    }
    
    int main() {
        int t;
        scanf("%d", &t);
        for (int i = 0; i < t; i++) {
            memset(cache, -1, sizeof(cache));
            scanf("%d%d", &m, &c);
            for (int j = 0; j < c; j++) {
                scanf("%d", &coin[j]);
            }
            printf("%d\n", howMany(c-1,m));
        }
        return 0;
    }
    

    7달 전
1개의 댓글이 있습니다.
  • Corea
    Corea

    cache[left] = ans 가 잘못되었습니다. 다음 데이터와 함께 손으로 코드를 따라가보면 알 수 있지 않으실까 싶어요.

    1
    40 2
    10 20

    7달 전 link
  • 댓글을 남기시려면 로그인하세요.