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

• 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];
}


8년 전
##### 2개의 댓글이 있습니다.

• WeissBlume

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

8년 전

• reniowood

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

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