COINS 문제 재질문 드립니다. ㅜ.ㅜ

  • iamhjoo
    iamhjoo

    계속 고민을 해봐도, COINS 문제 풀이에서 어디가 잘못됐는지를 못찾겠습니다. 일단 예제 입출력은 제대로 되지만, 오답이 계속 나옵니다.
    힌트 주실분 안계시나요??

    #include <iostream>
    using namespace std;
    #include <vector>
    #include <algorithm>
    
    #define MAX_COUNT 1000000007
    
    vector<int> coins;
    int cache[5000+1][100];
    
    int CountCoins(int sum, int type) {
        int& ret = cache[sum][type];
    
        if (sum == 0) return 1;
        if (sum < coins.back()) return 0;
        if (sum < 0)  return 0;
        if (ret != 0) return ret;
    
        for (int i=type; i < coins.size(); ++i)  {
            if (sum >= coins[i]) {
                ret += CountCoins(sum-coins[i], i);
            }
        }
    
        if (ret > MAX_COUNT) {
            ret %= MAX_COUNT;
        }
    
        return ret;
    }
    
    
    // 환전 금액 (1 <= M <= 5000)
    // 동전 종류의 개수 (1 <= C <= 100)
    
    int main() {
        int num_cases;
        cin >> num_cases;
    
        for (int n=0; n < num_cases; ++n) {
    
            // cache 초기화
            fill_n(cache[0], 5001*100, 0);
    
            // 동전 총합, 코인 개수
            int sum, ncoin;
            cin >> sum >> ncoin;
    
            // 동전 종류 벡터 생성
            for (int i=0; i<ncoin; i++) {
                int temp;
                cin >> temp;
                coins.push_back(temp);
            }
    
            // 코인을 정렬
            sort(coins.begin(), coins.end(), greater<int>());
            if (CountCoins(sum, 0) > MAX_COUNT)
                cout << CountCoins(sum, 0) % MAX_COUNT << endl;
            else
                cout << CountCoins(sum, 0) << endl;
    
            // 초기화
            coins.clear();
        }
    
        return 0;
    }
    


    11년 전
4개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    ret더하다 인트범위 넘어갈같네요


    11년 전 link
  • iamhjoo
    iamhjoo

    조언 감사합니다. 집에 가서 한번 고민해봐야겠네요.


    11년 전 link
  • yeonzzg
    yeonzzg

    답이 Max count일 경우도 문제가 되지 않을까요?


    10년 전 link
  • yeonzzg
    yeonzzg

    아.. 아니군요 문제에 명시된 대로 하셨군요 ㅠ


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.