CHRISTMAS 책 보고 공부중인데...

  • reniowood
    reniowood

    생각만으론 풀기 어려워서 책을 참고중인데, 어떤 미묘한 부분이 틀렸는지 계속 오답처리가 나오네요. 어떤 부분인지 궁금합니다 ㅠ

    #include <iostream>
    #include <numeric>
    #include <map>
    
    using namespace std;
    
    void calculate_partial_sums(unsigned int *D, int N, int K, unsigned int *partial_sums);
    unsigned int get_possible_purchase_number(int N, int K, unsigned int *partial_sums);
    int get_max_purchase_number(int N, int K, unsigned int *partial_sums);
    
    const int MAX_N = 100000;
    
    int main() {
        int T;
        int N, K;
        int Di;
        unsigned int *D, *partial_sums;
    
        cin >> T;
        while (T-- > 0) {
            cin >> N >> K;
    
            D = new unsigned int[N];
            partial_sums = new unsigned int[N + 1];
    
            for (int i=0; i<N; ++i) {
                scanf("%d", &Di);
    
                D[i] = Di;
            }
    
            calculate_partial_sums(D, N, K, partial_sums);
            cout << get_possible_purchase_number(N, K, partial_sums) << " " << get_max_purchase_number(N, K, partial_sums) << endl;
    
            delete[] D;
            delete[] partial_sums;
        }
    
        return 0;
    }
    
    void calculate_partial_sums(unsigned int *D, int N, int K, unsigned int *partial_sums) {
        partial_sums[0] = 0;
        for (int i=1; i<=N; ++i) {
            partial_sums[i] = (partial_sums[i-1] + D[i-1]) % K;
        }
    }
    
    unsigned int get_possible_purchase_number(int N, int K, unsigned int *partial_sums) {
        unsigned int possible_purchase_number = 0;
        map<int, unsigned int> occurance;
        map<int, unsigned int>::iterator iter;
    
        for (int i=0; i<=N; ++i) {
            if ((iter = occurance.find(partial_sums[i])) != occurance.end()) {
                iter->second++;
            } else {
                occurance.insert(make_pair(partial_sums[i], 1));
            }
        }
    
        for (iter=occurance.begin(); iter!=occurance.end(); ++iter) {
            possible_purchase_number += ((iter->second * (iter->second - 1)) / 2) % 20091101;
            possible_purchase_number %= 20091101;
        }
    
        return possible_purchase_number;
    }
    
    int get_max_purchase_number(int N, int K, unsigned int *partial_sums) {
        int max_purchase_numbers[MAX_N + 1];
        int same_partial_sums[MAX_N + 1];
    
        for (int i=0; i<=MAX_N; ++i) {
            max_purchase_numbers[i] = 0;
            same_partial_sums[i] = -1;
        }
    
        for (int i=0; i<=N; ++i) {
            if (i > 0) {
                max_purchase_numbers[i] = max_purchase_numbers[i-1];
            } else {
                max_purchase_numbers[i] = 0;
            }
    
            if (same_partial_sums[partial_sums[i]] != -1) {
                max_purchase_numbers[i] = max(max_purchase_numbers[i], 1 + max_purchase_numbers[same_partial_sums[partial_sums[i]]]);
            }
    
            same_partial_sums[partial_sums[i]] = i;
        }
    
        return max_purchase_numbers[N];
    }
    


    3년 전
2개의 댓글이 있습니다.
  • WeissBlume
    WeissBlume

    unsigned int의 경우 모든 경우의 수를 저장하기엔 표현 범위가 너무 작습니다. long long을 이용하세요.


    3년 전 link
  • reniowood
    reniowood

    답변 감사합니다! 잘 되네요 ㅠㅠ


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